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 <= 1000s consists of only lowercase English letters.Problem Overview: You receive a lowercase string s. You can replace any character with another lowercase letter. The goal is to transform the string into a palindrome while making the final result lexicographically smallest. The number of operations does not matter as long as the resulting string is the smallest possible palindrome.
Approach 1: Dynamic Programming (O(n²) time, O(n²) space)
This approach models the problem as building the smallest palindrome for every substring. Define dp[i][j] as the lexicographically smallest palindrome that can be formed from substring s[i..j]. If the characters at both ends match, extend the inner palindrome dp[i+1][j-1]. If they differ, replace the larger character with the smaller one and continue building inward. The DP table is filled for increasing substring lengths, combining results from previously solved subproblems.
Dynamic programming guarantees correctness for all substrings and demonstrates how local decisions affect the global lexicographic order. However, storing intermediate palindromes makes it memory heavy and slower than necessary. This method is mainly educational because the problem structure actually allows a simpler greedy observation. Concepts here overlap with common string DP problems where substrings are evaluated independently.
Approach 2: Iterative Two-Pointer Greedy (O(n) time, O(1) space)
The optimal observation: for every mirrored pair (i, j), the lexicographically smallest palindrome always uses the smaller of the two characters. Start two pointers at the beginning and end of the string. If s[i] == s[j], keep them unchanged. If they differ, replace both with min(s[i], s[j]). Move the pointers inward and repeat until they meet.
This works because lexicographic order depends on the earliest differing position. By forcing the smaller character at each mirrored pair, you minimize the string as early as possible without breaking the palindrome property. No backtracking or substring comparisons are needed. The algorithm scans the string once and modifies characters in place, making it both fast and memory efficient. This pattern is common in two pointers problems and relies on a simple greedy choice at every step.
Recommended for interviews: The iterative two-pointer greedy solution is what interviewers expect. It shows you recognize that lexicographic minimization can be decided locally for each mirrored pair. Mentioning the DP formulation demonstrates deeper reasoning about substring construction, but implementing the O(n) greedy approach proves you can simplify the problem once the key insight appears.
This approach involves using dynamic programming to store solutions of subproblems and build up the solution to the original problem. This is beneficial when the problem can be broken down into overlapping subproblems with optimal substructures.
This C program solves the Fibonacci sequence using dynamic programming. It uses a memoization array dp to store already computed Fibonacci numbers to avoid redundant calculations.
Time Complexity: O(n) because each number is computed only once, Space Complexity: O(n) for the storage array.
This approach converts the recursive solution into an iterative one. By using two variables to store intermediate Fibonacci numbers, we can achieve O(1) space complexity while maintaining a time complexity of O(n).
The C program uses an iterative approach to solve Fibonacci numbers. It reduces space usage by just maintaining two variables to track past computations.
Time Complexity: O(n), Space Complexity: O(1).
We use two pointers i and j to point to the beginning and end of the string, initially i = 0, j = n - 1.
Next, each time we greedily modify s[i] and s[j] to their smaller value to make them equal. Then we move i one step forward and j one step backward, and continue this process until i \ge j. At this point, we have obtained the smallest palindrome string.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | Time Complexity: O(n) because each number is computed only once, Space Complexity: O(n) for the storage array. |
| Approach 2: Iterative Solution | Time Complexity: O(n), Space Complexity: O(1). |
| Greedy + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n²) | When exploring substring-based palindrome construction or demonstrating DP reasoning |
| Iterative Two-Pointer Greedy | O(n) | O(1) | Best for interviews and production code due to linear scan and constant memory |
Lexicographically Smallest Palindrome | leetcode Weekly 346 | Leetcode Easy • BinaryMagic • 3,122 views views
Watch 9 more video solutions →Practice Lexicographically Smallest Palindrome with our built-in code editor and test cases.
Practice on FleetCode