We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Highest Value Palindrome
  5. Discussions

Highest Value Palindrome

  • wilsonthongwk
     + 0 comments

    This is a solution with time complexity = O(N) and space complexity = O(N). It passes all test cases.

    the solution finds the answer in two rounds. - 1st round: convert s to a valid Palindrome using fewest number of changes; - 2nd round: convert s to a highest number using the remaining available changes.

    1st round finds each char-pair using two indexes, one going from left->right, and one going from right->left.

    2nd round use two indexes to change the leftmost, and rightmost digit to '9'.

    several special cases need to be considered in order to pass all test cases. - case A: if a char at s[i] has been changed once, it is again changed to 9 in 2nd round, we need to make sure these two "actions" is counted as only one "changes". - case B: 2nd round needs to take care when s[i] itself is 9 already

    see comments in the code below for all details

    string highestValuePalindrome(string s, int n, int k) {
    
    // change to true when the 's' is checked to be a valid palindrome
    bool isValid = false;
    // mark touched[i] to true if s[i] is changed. thus 
    // we can change s[i] again and again and still use up only one k
    vector<bool> touched(n, false);
    
    // 1st round - use k to turn 's' into valid palindrome
    int l=0, r=s.size()-1; // the right and left index to s
    while (k>=0 and l<=r) {
        // whenever s[l]] != s[r], one of them need to changed
        // always change the smaller digit to the larger one
        if (s[l] != s[r]) {
            char largerCh = max(s[l], s[r]);
            touched[l] = largerCh != s[l];
            touched[r] = largerCh != s[r];
            s[l] = largerCh;
            s[r] = largerCh;
            --k;
        }
        ++l;
        --r;
    }
    isValid = l>r and k>=0;
    cout << "after 1st round - " << s << endl;
    
    // 2nd round - use remaining k to maximize 's'
    l=0;
    r=s.size()-1;
    int kToUse = 0;
    while (isValid and k>=0 and l<=r) {
        // change MSB to '9' whenever we still have k to use
        // note change we can also change s[i] without using any k
        // if touched[i] is true. also if s[i] is already '9' we 
        // don't need to change it any bigger
        
        kToUse = 0;
        kToUse += (s[l] != '9') and (not touched[l]);
        kToUse += (r != l) and (s[r] != '9') and (not touched[r]);     
        if (k >= kToUse) {
            s[l] = '9';
            s[r] = '9'; 
            k -= kToUse;
        }
        ++l;
        --r;
    }
    
    if (isValid) return s;
    else return "-1";
}