Lexicographically Smallest Palindrome

Let’s break down the problem to make the given string a palindrome with the minimum number of operations and ensure it’s lexicographically smallest.

1. Convert the input string into a list: Since strings are immutable, converting the string into a list of characters will facilitate modification.

2. Use two pointers to check characters: Start with two pointers, one pointing at the beginning of the string and the other at the end.

3. Compare characters and replace: Compare the characters at both pointers. If they are not the same, replace the character that is lexicographically larger with the smaller one. Keep track of the number of changes made.

4. Move pointers: Increment the start pointer and decrement the end pointer, then repeat step 3 until the pointers meet.

5. Convert the list back to a string: Once the characters are modified, convert the list back into a string.

6. Return the result: The modified string is the lexicographically smallest palindrome that can be created.

Here is the implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        # Convert the string into a list of characters
        chars = list(s)

        # Initialize pointers for start and end
        start = 0
        end = len(s) - 1

        # Loop through the characters and compare
        while start <= end:
            # If characters are not the same, replace the larger one
            if chars[start] != chars[end]:
                if chars[start] > chars[end]:
                    chars[start] = chars[end]
                else:
                    chars[end] = chars[start]

            # Move the pointers
            start += 1
            end -= 1

        # Convert the list back to a string
        result = ''.join(chars)

        return result

The above code ensures that the string becomes a palindrome with the minimum number of changes, and the resulting palindrome is lexicographically smallest. The time complexity is O(n), where n is the length of the string, as we are iterating through the string once.