Lexicographically Smallest Palindrome
EasyPrompt
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 <= 1000sconsists of only lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach constructs the palindrome by iterating through the string and building a new result string. For each position i, it considers the character s.charAt(i) and its symmetric counterpart s.charAt(n-1-i). To satisfy the conditions of minimum operations and lexicographically smallest result, the smaller of these two characters is chosen. The main drawback of this method is using string concatenation inside a loop in Java, which is very inefficient and leads to quadratic time complexity.
Algorithm
- Initialize an empty string,
palindrome.<br>* Iterate with an indexifrom0ton-1, wherenis the length of the input strings.<br>* In each iteration, get the character at the current index,char1 = s.charAt(i), and the character at the symmetric index,char2 = s.charAt(n - 1 - i).<br>* Append the lexicographically smaller ofchar1andchar2to thepalindromestring.<br>* After the loop completes, return thepalindromestring.
Walkthrough
This approach correctly identifies that the character at any position i in the final palindrome should be the minimum of the original characters at i and n-1-i. It then builds the resulting string character by character from left to right.<br><br>The inefficiency stems from the implementation detail of using the += operator for string concatenation within a loop. In Java, strings are immutable. Each concatenation operation result += char creates a completely new string object and copies all the characters from the old result string plus the new character. If the loop runs N times, the total number of copy operations is proportional to the sum 1 + 2 + ... + (N-1), which results in an O(N^2) time complexity.<br><br>```java
class Solution {
public String makeSmallestPalindrome(String s) {
int n = s.length();
String palindrome = ""; // Inefficient string building
for (int i = 0; i < n; i++) {
char char1 = s.charAt(i);
char char2 = s.charAt(n - 1 - i);
if (char1 < char2) {
palindrome += char1;
} else {
palindrome += char2;
}
}
return palindrome;
}
}
Complexity
Time
O(N^2), where N is the length of the string. The loop runs N times, and string concatenation inside the loop takes O(N) time on average, leading to a quadratic overall complexity.
Space
O(N^2) in many Java environments. During the loop, intermediate strings of lengths 1, 2, ..., N-1 are created and discarded. The final output string occupies O(N) space, but the peak space usage during execution can be much higher.
Trade-offs
Pros
The logic is straightforward to conceptualize.
Cons
Extremely inefficient in terms of time and space.
Will likely cause a 'Time Limit Exceeded' (TLE) error for constraints like N=1000.
This is the optimal approach, utilizing a two-pointer technique to achieve linear time complexity. It iterates through the string from both ends simultaneously, moving inwards. By converting the immutable string to a mutable char array, it can perform modifications efficiently. This method ensures minimum operations and the lexicographically smallest result in a single pass.
Algorithm
- Convert the input string
sinto a character array,chars.<br>* Initialize two pointers:left = 0andright = s.length() - 1.<br>* Loop as long asleftis less thanright.<br>* Inside the loop, comparechars[left]andchars[right].<br>* If they are different, set both positions to be the smaller of the two characters. For instance, ifchars[left] < chars[right], setchars[right] = chars[left]. Otherwise, setchars[left] = chars[right].<br>* Move the pointers towards the center by incrementingleftand decrementingright.<br>* After the loop, create a new string from the modifiedcharsarray and return it.
Walkthrough
To make a string a palindrome, the character at index i must equal the character at n-1-i. If they differ, we must change at least one. To minimize operations, we perform one change. To get the lexicographically smallest palindrome, we must make both positions equal to the smaller of the two original characters. This ensures the character at the earlier index i is as small as possible.<br><br>The two-pointer approach is a natural fit for this symmetric problem. A left pointer starts at the beginning, and a right pointer starts at the end. They move towards each other. At each step, they ensure the characters chars[left] and chars[right] are made equal to the smaller of the two, thus building the lexicographically smallest palindrome.<br><br>Since strings are immutable in Java, the input string is first converted to a char array to allow for efficient in-place modifications. After the two-pointer traversal is complete, the array is converted back to a string.<br><br>```java
class Solution {
public String makeSmallestPalindrome(String s) {
char[] chars = s.toCharArray();
int left = 0;
int right = s.length() - 1;
while (left < right) { if (chars[left] != chars[right]) { if (chars[left] < chars[right]) { chars[right] = chars[left]; } else { chars[left] = chars[right]; } } left++; right--; } return new String(chars);}}
Complexity
Time
O(N), where N is the length of the string. The process involves a single pass through roughly half of the string. Converting to and from a char array also takes O(N) time.
Space
O(N). An additional character array of size N is required to store the mutable version of the string, as strings are immutable in Java.
Trade-offs
Pros
Highly efficient with linear time complexity.
Optimal solution for this problem.
Easy to implement and understand.
Cons
Requires extra space for the character array due to string immutability in Java. This is generally an accepted trade-off.
Solutions
Solution
class Solution {public String makeSmallestPalindrome(String s) { char[] cs = s.toCharArray(); for (int i = 0, j = cs.length - 1; i < j; ++i, --j) { cs[i] = cs[j] = (char)Math.min(cs[i], cs[j]); } return new String(cs); }}class Solution {public: string makeSmallestPalindrome(string s) { for (int i = 0, j = s.size() - 1; i < j; ++i, --j) { s[i] = s[j] = min(s[i], s[j]); } return s; }};class Solution: def makeSmallestPalindrome(self, s: str) -> str: cs = list(s) i, j = 0, len(s) - 1 while i < j: cs[i] = cs[j] = min(cs[i], cs[j]) i, j = i + 1, j - 1 return "" . join(cs)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.