Finding the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to given string s

Question

I got stumped by this question during a coding challenge and I haven't come up with promising ideas for how to solve it. I am looking for hints or approaches to solve the problem, not necessarily the code.

Given a string s find the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to s. Strings may contain only lowercase English letters.

Examples:
For s = "cbaba", the output should be smallestPalindrome(s) = "cbabc"
For s = "abcbc", the output should be smallestPalindrome(s) = "abdba"

Trickier test cases:
input: "xgdfcs", output: "xgeegx"
input: "aazzzzba", output: "abaaaaba"
input: "aiyudauzzzzuaduyie", output: "aiyudavaaaavaduyia"

Guaranteed constraints:
4 ≤ s.length ≤ 5x10^5.

My previous approach was to:

1. Check if word is a palindrome by moving two pointers (i, j) at both ends of the word towards the middle.
2. If the two characters don't match, either set i-th character equal to the j-th, viceversa, OR set both equal to some character that appears later in the alphabet.

...but I couldn't figure out how to decide which option in step 2) should be taken. Maybe there's a better approach to it.

I'm trying to avoid posting the name of the company that posed me this question to prevent future interviewees from knowing the answer in advance, so you can assume I found the question here:

Source: https://codelearn.io/training/detail/33520

Answer 1

Let's assume the length is even for now. Split the word up into two equal parts, $w = lr$. Let $l^R$ be the reverse of $l$.

If $l^R = r$, we are done immediately. Otherwise, if $r < l^{R}$ we can set $r$ equal to $l^R$. The more involved case is when $l^R < r$. In that case we will need to increment $l$ by one (view the lowercase English words as a base-26 number - this exactly matches lexicographic order), after which we can set $r$ equal to the reversed left hand side and we'll still be lexicographically bigger.

Now if our original word was odd in length we apply the exact same process, except when we shouldn't increment $l$ by one but start the increment one more to the right: at the middle element instead.

Some example code in C:

void increment_base26(char* s, int len) {
    int i = len - 1;
    while (i >= 0) {
        if (s[i] == 'z') s[i] = 'a'; // Wrap around and carry.
        else { s[i] += 1; break; }
        i -= 1;
    }
}

void reverse(char *s, int len) {
    for (int i = 0; i < len - 1 - i; ++i) {
        char t = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = t;
    }
}

void next_lexicographic_palindrome(char* s) {
    int len = strlen(s);
    int half = len / 2; // Rounds down.
    int half_plus_mid = half + (len % 2);
    reverse(s, half);                                // Compute l^R.
    int cmp = strncmp(s, s + half_plus_mid, half);   // Compare l^R and r.
    if (cmp > 0) memcpy(s + half_plus_mid, s, half); // l^R > r, can just copy over l^R.
    reverse(s, half);                                // Undo l^R -> l.
    if (cmp >= 0) { return; }                        // Simple cases l^R >= handled.
    increment_base26(s, half_plus_mid);              // Increment left + mid.
    reverse(s, half);                                // Copy over the new l^R to r.
    memcpy(s + half_plus_mid, s, half);
    reverse(s, half);
}

Answer 2

This is a very interesting problem, here is my implementation in Python

Maybe we can combine those 2 cases in 1 scenario :

def increase_one(input_):
    s = list(input_)
    for i in range(len(s)-1,-1,-1):
        if s[i]=='z':
            s[i]='a'
        else:
            s[i]=chr(ord(s[i])+1)
            break
    return ''.join(s)

def run(string):
    if not string:
        return ""
    
    left,right = 0,len(string)-1
    length = len(string)
    
    index = length//2
    if length%2==1:
        left,right = string[:index],string[index+1:]
        if right<left[::-1]:
            return left+string[index]+left[::-1]
        else:
            new_left = increase_one(string[:index+1])
            return new_left+new_left[:-1][::-1]
    else:
        left,right = string[:index],string[index:]
        if right<left[::-1]:
            return left+left[::-1]
        else:
            new_left = increase_one(left)
            return new_left+new_left[::-1]
        
if __name__=='__main__':
    print(run('cbaba'))
    print(run('abcbc'))
    print(run('xgdfcs'))
    print(run('aazzzzba'))
    print(run('aiyudauzzzzuaduyie'))