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
sfind the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to
s. Strings may contain only lowercase English letters.
s = "cbaba", the output should be
smallestPalindrome(s) = "cbabc"
s = "abcbc", the output should be
smallestPalindrome(s) = "abdba"
Trickier test cases:
4 ≤ s.length ≤ 5x10^5.
My previous approach was to:
- Check if word is a palindrome by moving two pointers (
j) at both ends of the word towards the middle.
- 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: