Lexicographically Smallest Palindrome Solution Code in C++/Java/Python/JavaScript
Problem
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
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'.
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".
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 only lowercase English letters.
Figuring out the "Lexicographically Smallest Palindrome solution" requires a bit of observations and pen and paper work. We need to take examples and then figure out the working algorithm.
Optimal Approach
Intuition
What is a Palindrome?
The string which when read/wrote from left to right equals when read/wrote from right to left.
If we are asked to make the string "learn" as the palindrome string. How can we make it ??
It's quite obvious that "learn" is not a palindromic string. We need to alter few characters of the word "learn" to make it the lexicographically smallest palindrome.
We are familiar with checking whether a string is a palindrome by taking two pointers and traversing from left to right.
For the given problem statement for "Lexicographically Smallest Palindrome", we will be following the same two pointer approach to figure out the Lexicographically Smallest Palindrome.
Whenever we try to figure out any algorithm, we must start from the simplest string possible and then move forward with the complex strings in generating the output and checking the logical part.
Since, the string length can be "1 <= s.length <= 1000".
Suppose s="a". It's a palindrome.
Our first observation comes out to be, that if the string length is 1, it's a palindrome, hence we will return the same string as our answer!!
Suppose the string s="cd".
There are two ways to make the string palindrome. One is changing 'c' to 'd' and the other being altering 'd' to 'c' i.e.
s="cd" can be either changed to "cc" or "dd". Which is the lexicographically smaller among the 2 ?
It's "cc".
What did we do?
We checked the left-most character and the right-most character of the string "cd". They were not equal, so in order to form the lexicographically smallest palindrome, we had to alter 'd' to 'c' because ASCII value of 'c' is smaller than 'd'.
What logic can we derive from this observation ?
If we encounter two unequal characters at the leftmost and the rightmost position, we will compare the two characters and then choose the character with lesser ASCII value to be present at both the indices.
Suppose, s="abccda".
Our first inequality comes when the left pointer is at index 1 and the right pointer is at index 4 as shown in bolded figures of s="abccda".
We will compare the ASCII values of 'b' and 'd'. It comes out to be 'b' which is lexicographically smaller. So, we alter the character at position 4 to 'b' . Hence, the new string becomes s="abccba".
Let's now check the algorithm to write the code.
Lexicographically Smallest Palindrome Algorithm
- We will traverse the string character by character.
- We will be using two pointers to traverse the string from left and right respectively.
- Whenever the characters at left and right of the string doesn't match, we will compare the two characters and modify the index which has higher ASCII values.
- After the complete iteration we will have the "Lexicographically Smallest Palindrome".
Let's now see how we can code it up!!
Approach
Convert the String to a Character Array: Take the input string s and convert it into a character array arr for easy modification.
Initialize Two Pointers
- Set left = 0 (pointing to the first character).
- Set right = s.length() - 1 (pointing to the last character).
Iterate Until the Pointers Meet: While left < right:
- If arr[left] is not equal to arr[right]: Set both arr[left] and arr[right] to the smaller of the two characters.
- Move left one step forward (left++).
- Move right one step backward (right--).
Convert the Modified Array Back to a String: Return the updated character array as a new string.
Let us understand this with a video.
Dry-Run
Input: s="zaccdy"
Output: "yaccay"
Initial Setup:
- Convert string "zaccdy" to a character array:
arr = ['z', 'a', 'c', 'c', 'd', 'y'] - Initialize pointers:
- left = 0, right = 5
Iteration Steps:
- Iteration 1:
- Compare arr[left] = 'z' and arr[right] = 'y'
- Replace both with 'y' (smaller of the two)
- Updated arr = ['y', 'a', 'c', 'c', 'd', 'y']
- Move left → 1, right → 4
- Iteration 2:
- Compare arr[left] = 'a' and arr[right] = 'd'
- Replace both with 'a' (smaller of the two)
- Updated arr = ['y', 'a', 'c', 'c', 'a', 'y']
- Move left → 2, right → 3
- Iteration 3:
- Compare arr[left] = 'c' and arr[right] = 'c'
- No change needed (already equal)
- Move left → 3, right → 2 (loop exits)
Final Step:
- Convert arr back to a string → "yac cay"
Output: "yaccay"
Lexicographically Smallest Palindrome Solution
Now, let's checkout the Lexicographically Smallest Palindrome solution in c++, Java, Python and JavaScript
"Lexicographically Smallest Palindrome" Code in all Languages.
1. Lexicographically Smallest Palindrome solution in C++ Try on Compiler
#include <iostream>
using namespace std;
class Solution {
public:
string makeSmallestPalindrome(string s) {
// Convert the string into a character array (string in C++)
int left = 0, right = s.length() - 1;
// Iterate while left pointer is less than right pointer
while (left < right) {
// If characters at both ends are different, replace them with the smaller one
if (s[left] != s[right]) {
s[right] = s[left] = min(s[left], s[right]);
}
// Move the left pointer forward and the right pointer backward
left++;
right--;
}
// Return the modified string
return s;
}
};
int main() {
// Prompt the user to enter a string
cout << "Enter a string: ";
string s;
cin >> s;
// Create an instance of Solution class
Solution solution;
// Call the method and print the resulting smallest palindrome
cout << "Smallest Palindrome: " << solution.makeSmallestPalindrome(s) << endl;
return 0;
}
2. Lexicographically Smallest Palindrome II in Java Try on Compiler
import java.util.Scanner;
class Solution {
public String makeSmallestPalindrome(String s) {
// Convert the string into a character array
char[] arr = s.toCharArray();
// Initialize two pointers, one at the beginning and one at the end
int left = 0, right = s.length() - 1;
// Iterate while left pointer is less than right pointer
while (left < right) {
// If characters at both ends are different, replace them with the smaller one
if (arr[left] != arr[right]) {
arr[right] = arr[left] = (char) Math.min(arr[left], arr[right]);
}
// Move the left pointer forward and the right pointer backward
left++;
right--;
}
// Convert the modified character array back to a string and return
return new String(arr);
}
public static void main(String[] args) {
// Create a scanner to read input from the user
Scanner scanner = new Scanner(System.in);
// Prompt the user to enter a string
System.out.print("Enter a string: ");
String s = scanner.next();
// Create an instance of Solution class
Solution solution = new Solution();
// Call the method and print the resulting smallest palindrome
System.out.println("Smallest Palindrome: " + solution.makeSmallestPalindrome(s));
// Close the scanner
scanner.close();
}
}
3. Lexicographically Smallest Palindrome solution in Python Try on Compiler
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
# Convert the string into a list of characters (since strings are immutable)
arr = list(s)
# Initialize two pointers, one at the beginning and one at the end
left, right = 0, len(s) - 1
# Iterate while left pointer is less than right pointer
while left < right:
# If characters at both ends are different, replace them with the smaller one
if arr[left] != arr[right]:
arr[right] = arr[left] = min(arr[left], arr[right])
# Move the left pointer forward and the right pointer backward
left += 1
right -= 1
# Convert the modified list back to a string and return
return "".join(arr)
if __name__ == "__main__":
# Prompt the user to enter a string
s = input("Enter a string: ")
# Create an instance of Solution class
solution = Solution()
# Call the method and print the resulting smallest palindrome
print("Smallest Palindrome:", solution.makeSmallestPalindrome(s))
4. Lexicographically Smallest Palindrome solution in JavaScript Try on Compiler
const fs = require("fs");
class Solution {
makeSmallestPalindrome(s) {
// Convert the string into a character array
let arr = s.split("");
// Initialize two pointers, one at the beginning and one at the end
let left = 0, right = s.length - 1;
// Iterate while left pointer is less than right pointer
while (left < right) {
// If characters at both ends are different, replace them with the smaller one
if (arr[left] !== arr[right]) {
arr[right] = arr[left] = String.fromCharCode(
Math.min(arr[left].charCodeAt(0), arr[right].charCodeAt(0))
);
}
// Move the left pointer forward and the right pointer backward
left++;
right--;
}
// Convert the modified array back to a string and return
return arr.join("");
}
}
// Read input from a file (assuming input.txt contains the input string)
const input = fs.readFileSync("input.txt", "utf8").trim();
// Create an instance of Solution class
const solution = new Solution();
// Call the method and print the resulting smallest palindrome
console.log("Smallest Palindrome:", solution.makeSmallestPalindrome(input));
Lexicographically Smallest Palindrome Complexity Analysis
Time Complexity: O(n)
- The function processes the input string s once using two pointers (left and right).
- In each iteration, the pointers move closer, performing at most one comparison and one assignment per iteration.
- The loop runs for O(N/2) ≈ O(N) iterations in the worst case, where N is the length of the string.
Thus,
Time Complexity: O(N)
Space Complexity: O(n)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used apart from the input storage.
- The function modifies the string in place (or in a mutable character array) in Java, C++, and JavaScript.
- In Python, since strings are immutable, a list is created to store the modified string, but this list is of size O(N).
- Other than this, only a few integer variables (left, right) are used, which take O(1) space.
Thus,
Auxiliary Space Complexity: O(N) in Python, O(1) in Java, C++, and JavaScript
Total Space Complexity
Total space complexity includes both input storage and auxiliary space.
- Input Storage: The input string requires O(N) space.
- Auxiliary Space:
- Java, C++, JavaScript: Modify the string in place, so extra space is O(1).
- Python: Uses a list of O(N) extra space.
Thus,
Total Space Complexity:
- O(N) in Java, C++, and JavaScript (because of input storage).
- O(N) in Python (input storage + list used for modification).
Similar Problems
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.