Highest Value Palindrome

• Time : O(n)
• Space : O(n)

c++

string highestValuePalindrome(string s, int n, int k) {
    int l = 0, r = n - 1;
    vector<bool> modified(s.length(), false);
    while(l <= r) {
        if(s[l] != s[r]) {
            if(!k) return "-1";
            s[l] = s[r] = max(s[l], s[r]);
            modified[l] = modified[r] = true;
            k--;
        }
        l++,r--;
    }
    l = 0, r = s.length() - 1;
    while(l <= r and k) {
        if(l == r) {
            if(s[l] != '9') s[l] = '9';
        } else if(s[l] != '9') {
            if(modified[l]) {
                s[l] = s[r] = '9'; k -= 1;
            } else if(k >= 2) {
                s[l] = s[r] = '9'; k -= 2;
            }
        }
        l++, r--;
    }
    return s;
}