Lexicographically Smallest Palindrome

Difficulty: Easy | Acceptance: 81.40% | Paid: No Topics: Two Pointers, String, Greedy

You are given a string s consisting only of lowercase English letters.

In one move, you can replace any character with any other lowercase English letter.

Return the lexicographically smallest palindrome string you can obtain by applying the operation on s at most once per character.

Table of Contents

• Examples
• Constraints
• Two Pointers (In-place Modification)
• Two Pointers (String Construction)

Examples

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”.

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 lowercase English letters.

Two Pointers (In-place Modification)

Intuition To form a palindrome, the character at the left pointer must match the character at the right pointer. To ensure the result is lexicographically smallest, if the characters differ, we should replace the larger character with the smaller one.

Steps

• Convert the string into a mutable character array (or list).
• Initialize two pointers, left at 0 and right at n - 1.
• While left is less than right:
  • If arr[left] is greater than arr[right], set arr[left] to arr[right].
  • Otherwise, if arr[right] is greater than arr[left], set arr[right] to arr[left].
  • Increment left and decrement right.
• Convert the character array back to a string and return it.

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        s_list = list(s)
        l, r = 0, len(s) - 1
        while l < r:
            if s_list[l] > s_list[r]:
                s_list[l] = s_list[r]
            elif s_list[r] > s_list[l]:
                s_list[r] = s_list[l]
            l += 1
            r -= 1
        return "".join(s_list)

Complexity

• Time: O(n), where n is the length of the string. We traverse the string once.
• Space: O(n) to store the character array (or list), though C++ modifies in-place using O(1) extra space.
• Notes: This approach is efficient and directly modifies the input structure to achieve the result.

Two Pointers (String Construction)

Intuition Instead of modifying the original array in place, we can construct a new result array. We iterate from both ends, pick the lexicographically smaller character between the two pointers, and place it at both the corresponding left and right positions in the new array.

Steps

• Initialize a result array (or list) of the same size as s.
• Initialize two pointers, left at 0 and right at n - 1.
• While left is less than or equal to right:
  • Determine the min_char as the minimum of s[left] and s[right].
  • Set result[left] and result[right] to min_char.
  • Increment left and decrement right.
• Join the result array into a string and return it.

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        n = len(s)
        res = [''] * n
        l, r = 0, n - 1
        while l <= r:
            min_char = min(s[l], s[r])
            res[l] = min_char
            res[r] = min_char
            l += 1
            r -= 1
        return "".join(res)

Complexity

• Time: O(n), where n is the length of the string. We traverse the string once.
• Space: O(n) to store the new result array.
• Notes: This approach is conceptually clean as it builds the answer from scratch without mutating the original input, though it uses slightly more memory than the in-place C++ solution.