Teaching Kids Programming – Algorithms to Find the Lexicographically Smallest Palindrome

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a string s consisting of lowercase English letters, and you are allowed to perform operations on it. In one operation, you can replace a character in s with another lowercase English letter. Your task is to make s a palindrome with the minimum number of operations possible. If there are multiple palindromes that can be made using the minimum number of operations, make the lexicographically smallest one. A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.

Return the resulting palindrome string.

Example 1:
Input: s = “egcfe”
Output: “efcfe”
Explanation: The minimum number of operations to make “egcfe” a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is “efcfe”, by changing ‘g’.

Example 2:
Input: s = “abcd”
Output: “abba”
Explanation: The minimum number of operations to make “abcd” a palindrome is 2, and the lexicographically smallest palindrome string we can get by modifying two characters is “abba”.

Example 3:
Input: s = “seven”
Output: “neven”
Explanation: The minimum number of operations to make “seven” a palindrome is 1, and the lexicographically smallest palindrome string we can get by modifying one character is “neven”.

Constraints:
1 <= s.length <= 1000
s consists of only lowercase English letters.

Algorithms to Find the Lexicographically Smallest Palindrome

A palindrome is that a string is equal to its reverse version for example, abba, racecar. There are multiple ways (even unlimited) to change the existing input string to a palindrome. But there is only one smallest (Lexicographically) palindrome.

The key thing to solve this problem is to choose from left to right, the smaller character, and replace its corresponding. For example, for given input string rice, the smallest palindrome is ecce because we compare (r, e) and (i, c) to choose the smaller one.

The following uses a two pointer algorithm and we append the smaller character to a list. However, we need to check if it is an odd or even palindrome, then we need to reverse and map the second half.

The time/space complexity is O(N).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        L = 0
        R = len(s) - 1
        ans = []
        while L <= R:
            ans.append(min(s[L], s[R]))            
            L += 1
            R -= 1
        if len(s) & 1:
            ans.extend(ans[::-1][1:])
        else:
            ans.extend(ans[::-1])
        return "".join(ans)

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        L = 0
        R = len(s) - 1
        ans = []
        while L <= R:
            ans.append(min(s[L], s[R]))            
            L += 1
            R -= 1
        if len(s) & 1:
            ans.extend(ans[::-1][1:])
        else:
            ans.extend(ans[::-1])
        return "".join(ans)

We can iterate over the entire string and then push the smaller one of index i and index n-i-i (corresponding one) to the result, and the finally return the string by join. In Python, we use the ~i which is getting the Two’s Complement, so ~i is equal to -(i+1) for example ~0=-1 and ~1=-2, and In python, we use -1 to reference the last character, and -2 to reference the second last character.

1
2
3
4
5
6
7

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        ans = []
        n = len(s)
        for i in range(n):
            ans.append(min(s[i], s[~i]))
        return "".join(ans)

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        ans = []
        n = len(s)
        for i in range(n):
            ans.append(min(s[i], s[~i]))
        return "".join(ans)

Another implementation is zip the string and the reversed version via [::-1] and then compare each pair, see the following one-liner.

1
2
3

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        return "".join(map(min, zip(s, s[::-1])))

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        return "".join(map(min, zip(s, s[::-1])))

If we convert the string (immutable) to a list, then we can modify it in-place, then we only need to iterate over the first half.

1
2
3
4
5
6
7
8

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        s = list(s)
        n = len(s)
        for i in range(n//2):
            # s[i] = s[-i-1] = min(s[i], s[-i-1])
            s[i] = s[~i] = min(s[i], s[~i])            
        return "".join(s)

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        s = list(s)
        n = len(s)
        for i in range(n//2):
            # s[i] = s[-i-1] = min(s[i], s[-i-1])
            s[i] = s[~i] = min(s[i], s[~i])            
        return "".join(s)

–EOF (The Ultimate Computing & Technology Blog) —