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 tos
. Strings may contain only lowercase English letters.
Examples:
Fors = "cbaba"
, the output should besmallestPalindrome(s) = "cbabc"
Fors = "abcbc"
, the output should besmallestPalindrome(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:
- Check if word is a palindrome by moving two pointers (
i
,j
) at both ends of the word towards the middle. - If the two characters don't match, either set
i
-th character equal to thej
-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: