LeetCode Problem 2697

Difficulty: 🟢 Easy
Topics: Two Pointers, String, Greedy

Solution

LeetCode 2697, Lexicographically Smallest Palindrome

Problem Understanding

The problem gives us a string s consisting only of lowercase English letters. We are allowed to replace characters in the string with other lowercase letters. Our goal is to transform the string into a palindrome.

A palindrome is a string that reads the same forward and backward. This means that for every position i, the character at position i must match the character at position n - 1 - i, where n is the length of the string.

The challenge has two requirements that must both be satisfied:

1. Use the minimum number of replacement operations.
2. Among all palindromes achievable with the minimum number of operations, return the lexicographically smallest one.

Lexicographical order works the same way as dictionary order. For example:

• "abba" is smaller than "acca" because 'b' < 'c' at the first differing position.
• "apple" is smaller than "apply" because 'e' < 'y'.

The input is a single string whose length can be as large as 1000. Since the string is relatively small, we can afford linear or quadratic algorithms comfortably. However, the problem has a very clean greedy solution that works in linear time.

The key observation is that each pair of mirrored characters determines whether an operation is needed. For example:

• If the pair already matches, no operation is necessary.
• If the pair differs, at least one character must change.

To minimize operations, we should change exactly one character in every mismatched pair.

Important edge cases include:

• Strings of length 1, which are already palindromes.
• Strings that are already palindromes.
• Odd length strings, where the middle character does not need to be changed.
• Pairs with different characters, where choosing the smaller character produces the lexicographically smallest answer.

The problem guarantees that all characters are lowercase English letters, so comparisons are straightforward.

Approaches

Brute Force Approach

A brute force solution would try all possible palindromes obtainable from the string and select the one requiring the fewest modifications. Among those, it would choose the lexicographically smallest palindrome.

This approach is theoretically correct because it explores every valid possibility. However, it is computationally infeasible. A string of length n has 26^n possible strings over lowercase letters. Even restricting ourselves to palindromes still leaves an enormous search space of approximately 26^(n/2).

For n = 1000, this is impossible to compute.

Optimal Greedy Two Pointer Approach

The important insight is that mirrored positions are independent of each other.

For every pair (left, right):

• If the characters are equal, we keep them unchanged.
• If the characters differ, we must perform exactly one replacement.

To minimize lexicographical order, we should keep the smaller character and replace the larger one.

For example:

• Pair ('d', 'a') becomes ('a', 'a')
• Pair ('g', 'f') becomes ('f', 'f')

This greedy choice is always optimal because lexicographical order is determined from left to right. Making the earlier character as small as possible guarantees the smallest overall string.

Using two pointers allows us to process the string in one pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(26^(n/2))	O(26^(n/2))	Enumerates all possible palindromes
Optimal	O(n)	O(n)	Two pointers with greedy replacement

Algorithm Walkthrough

1. Convert the string into a mutable array of characters because strings are immutable in Python and Go.
2. Initialize two pointers:

• left = 0
• right = len(s) - 1

3. While left < right, compare the characters at both positions.
4. If the characters are already equal:

• Do nothing because this pair already satisfies the palindrome condition.

5. If the characters are different:

• Find the smaller of the two characters.
• Replace both positions with that smaller character.
• This uses exactly one effective modification and guarantees the lexicographically smallest result.

6. Move the pointers inward:

• left += 1
• right -= 1

7. Continue until all mirrored pairs are processed.
8. Join the character array back into a string and return it.

Why it works

Every mismatched pair requires at least one modification. Replacing the larger character with the smaller one achieves the minimum number of changes because only one character in the pair changes.

Among all minimum operation solutions, choosing the smaller character minimizes the earliest differing position in the final string. Since lexicographical comparison prioritizes earlier characters, this greedy choice guarantees the lexicographically smallest palindrome.

Python Solution

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        characters = list(s)

        left = 0
        right = len(characters) - 1

        while left < right:
            smaller_char = min(characters[left], characters[right])

            characters[left] = smaller_char
            characters[right] = smaller_char

            left += 1
            right -= 1

        return "".join(characters)

The implementation begins by converting the string into a list of characters. This is necessary because Python strings cannot be modified in place.

Two pointers are used to process mirrored positions from the outside inward. For each pair, the algorithm computes the smaller character using min() and assigns that value to both positions.

If the characters are already equal, assigning the same value again causes no issues and keeps the logic simple and consistent.

Finally, the modified character list is joined back into a string and returned.

The implementation directly follows the greedy strategy described earlier and processes each character pair exactly once.

Go Solution

func makeSmallestPalindrome(s string) string {
    characters := []byte(s)

    left := 0
    right := len(characters) - 1

    for left < right {
        smallerChar := characters[left]

        if characters[right] < smallerChar {
            smallerChar = characters[right]
        }

        characters[left] = smallerChar
        characters[right] = smallerChar

        left++
        right--
    }

    return string(characters)
}

The Go implementation uses a byte slice because strings in Go are immutable. Since the input contains only lowercase English letters, byte manipulation is sufficient and efficient.

The logic is otherwise identical to the Python version. The smaller character is chosen manually using a comparison because Go does not provide a built in min function for bytes.

The final byte slice is converted back into a string before returning.

Worked Examples

Example 1

Input:

s = "egcfe"

Initial state:

Left Index	Right Index	Characters	Action	Result
0	4	e, e	Already equal	egcfe
1	3	g, f	Replace both with f	efcfe

Final output:

"efcfe"

Example 2

Input:

s = "abcd"

Initial state:

Left Index	Right Index	Characters	Action	Result
0	3	a, d	Replace both with a	abca
1	2	b, c	Replace both with b	abba

Final output:

"abba"

Example 3

Input:

s = "seven"

Initial state:

Left Index	Right Index	Characters	Action	Result
0	4	s, n	Replace both with n	neven
1	3	e, e	Already equal	neven

Final output:

"neven"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character pair is processed once
Space	O(n)	Mutable character array stores the modified string

The algorithm scans the string from both ends toward the center. Since each position is visited at most once, the runtime is linear.

The extra space comes from converting the immutable string into a mutable character array. No additional data structures proportional to input size are used.

Test Cases

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        characters = list(s)

        left = 0
        right = len(characters) - 1

        while left < right:
            smaller_char = min(characters[left], characters[right])

            characters[left] = smaller_char
            characters[right] = smaller_char

            left += 1
            right -= 1

        return "".join(characters)

solution = Solution()

assert solution.makeSmallestPalindrome("egcfe") == "efcfe"  # Example 1
assert solution.makeSmallestPalindrome("abcd") == "abba"  # Example 2
assert solution.makeSmallestPalindrome("seven") == "neven"  # Example 3

assert solution.makeSmallestPalindrome("a") == "a"  # Single character
assert solution.makeSmallestPalindrome("aa") == "aa"  # Already palindrome
assert solution.makeSmallestPalindrome("aba") == "aba"  # Odd length palindrome
assert solution.makeSmallestPalindrome("abcba") == "abcba"  # Larger palindrome
assert solution.makeSmallestPalindrome("zyxy") == "xyyx"  # Multiple replacements
assert solution.makeSmallestPalindrome("race") == "eaae"  # Lexicographically smallest choice
assert solution.makeSmallestPalindrome("bbbb") == "bbbb"  # All identical characters
assert solution.makeSmallestPalindrome("az") == "aa"  # Two different characters

Test	Why
"egcfe"	Validates single replacement case
"abcd"	Validates multiple replacements
"seven"	Validates odd length handling
"a"	Smallest possible input
"aa"	Already palindrome
"aba"	Middle character remains untouched
"abcba"	Confirms no unnecessary changes
"zyxy"	Tests multiple mismatched pairs
"race"	Verifies lexicographical minimization
"bbbb"	All characters identical
"az"	Simplest mismatched pair

Edge Cases

A single character string is an important edge case because it is automatically a palindrome. A careless implementation might incorrectly attempt pointer comparisons or modifications. This implementation handles it naturally because the loop condition left < right is false immediately.

Strings that are already palindromes can also cause subtle bugs if unnecessary replacements are made. For example, changing equal characters could accidentally increase the lexicographical value or waste operations. This solution leaves matching pairs unchanged because the minimum character of two identical letters is the same letter.

Odd length strings contain a middle character with no mirrored partner. Some implementations mistakenly modify or compare this center element. Here, the loop stops once left >= right, so the center character is never touched, which is correct because it does not affect the palindrome property.

Another important edge case occurs when mirrored characters differ significantly, such as 'z' and 'a'. A naive solution might always replace the left character or always replace the right character. That approach would not guarantee lexicographical minimality. By always choosing the smaller character for both positions, this implementation ensures the final palindrome is the smallest possible among all optimal solutions.