2697. Lexicographically Smallest Palindrome
Problem Description
The problem presents a scenario in which you have a string s
comprised entirely of lowercase English letters. The goal is to transform this string into a palindrome using a series of operations with two conditions:
- Minimize the number of operations.
- If multiple palindromes can be achieved with the same minimum number of operations, choose the one that is lexicographically smallest.
An operation is defined as replacing any single character in the string with another lowercase English letter. And finally, the concept of a lexicographically smaller string is explained: it's a string that has an earlier occurring letter at the first position where two strings differ.
Your task is to write a function that returns the resulting palindrome that satisfies the above conditions.
Intuition
Transforming a string into a palindrome means making the string the same when read forwards and backwards. A straightforward approach to doing this is to iterate over the string from both ends towards the center, comparing characters at symmetric positions.
If the characters at symmetric positions are different, you must choose which one to change to match the other. To satisfy the condition of lexicographical order, we should choose the smaller (earlier in the alphabet) of the two characters and set both positions to that character.
We continue this process until we reach the middle of the string. Since we operate on symmetric positions, the number of operations is inherently minimized, as each operation ensures that both the left and right sides match.
Knowing this, the implemented solution approach is as follows:
- We convert the string into a list of characters to allow in-place modification because strings in Python are immutable.
- We set two pointers,
i
andj
, at the start and end of the list, respectively. - We iterate, moving
i
forward andj
backward, and at each step, we compare the characters at these indices. - If they are not the same, we set both
cs[i]
andcs[j]
to the lexicographically smaller of the two characters. - We increment
i
and decrementj
and repeat this process untili
is no longer less thanj
. - We join the list back into a string and return it, which is the lexicographically smallest palindrome obtainable with the minimal number of operations.
Learn more about Two Pointers patterns.
Solution Approach
The solution makes use of a two-pointer approach and array manipulation. Here is a step-by-step breakdown of the algorithm:
-
Convert the Immutable String to a Mutable List: Python strings are immutable, meaning they cannot be changed after they are created. To overcome this, the string
s
is converted into a list of characterscs
usinglist(s)
. Lists allow in-place modification, which is necessary for our operations. -
Initialize Two Pointers: Two pointers
i
andj
are initialized. Pointeri
starts at the beginning of the list (index 0) andj
starts at the end of the list (indexlen(s) - 1
). These pointers will traverse the list from both ends towards the center. -
Iterate and Compare Characters: While
i
is less thanj
, indicating that we haven't reached the middle of the list, we compare the characters atcs[i]
andcs[j]
. -
Perform the Replacement: If the characters at these two positions are different, we find the lexicographically smaller character by using the
min(s[i], s[j])
function and set bothcs[i]
andcs[j]
to that character. -
Move the Pointers: After handling the characters at the current positions, we move
i
forward by 1 (i + 1
) andj
backward by 1 (j - 1
) to compare the next set of characters. -
Exit the Loop: The loop continues until
i
is not less thanj
. At this point, we have ensured that for every positioni
from the start to the middle of the list, there is a corresponding positionj
from the end to the middle wherecs[i]
andcs[j]
are identical—guaranteeing palindrome property. -
Return the Result: After exiting the loop, we have a list of characters representing our smallest lexicographically possible palindrome. We join this list back into a string with
"".join(cs)
and return this final palindrome string.
No additional complex data structures beyond the basic list and standard control structures (a while loop with two pointers) are used. The underlying pattern used is the two-pointer technique, which is a common strategy to compare and move towards the center from both ends of a sequence.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the following example to illustrate the solution approach:
Suppose we have the string s = "abzca"
. We want to transform this string into a palindrome using the least number of operations such that if there are multiple possible palindromes, we choose the lexicographically smallest one.
Following the solution steps:
-
Convert the Immutable String to a Mutable List: We convert
s
into a listcs = ['a', 'b', 'z', 'c', 'a']
. -
Initialize Two Pointers: We set
i = 0
at the beginning of the list andj = len(cs) - 1 = 4
at the end of the list. -
Iterate and Compare Characters:
- First iteration:
cs[i] = 'a'
andcs[j] = 'a'
, since they are the same, we don't need to perform any operations. Movei
to1
andj
to3
. - Second iteration: Now,
cs[i] = 'b'
andcs[j] = 'c'
. They are different, so we have to replace one of them. We choose the lexicographically smaller character, which is 'b', and set both positions to 'b':cs = ['a', 'b', 'z', 'b', 'a']
. Movei
to2
andj
to2
. - Since
i
andj
are the same value, we have reached the middle of the list and no further iterations are needed.
- First iteration:
-
Return the Result: The resulting list represents the palindrome
'abbba'
. We convert it back to a string and, therefore, the function would return"abbba"
.
Here, only one operation was needed to achieve the palindrome, and 'abbba'
is the lexicographically smallest palindrome that can be made from abzca
.
Solution Implementation
1class Solution:
2 def makeSmallestPalindrome(self, s: str) -> str:
3 # Initialize pointers for the start and end of the string.
4 left_pointer, right_pointer = 0, len(s) - 1
5 # Convert the string to a list of characters for easier manipulation.
6 char_list = list(s)
7
8 # Loop until the pointers meet in the middle or cross each other.
9 while left_pointer < right_pointer:
10 # If the characters at the current pointers don't match,
11 # replace them with the lexicographically smaller one to help
12 # create the smallest possible palindrome.
13 if s[left_pointer] != s[right_pointer]:
14 smaller_char = min(s[left_pointer], s[right_pointer])
15 char_list[left_pointer] = smaller_char
16 char_list[right_pointer] = smaller_char
17
18 # Move the pointers closer to the center.
19 left_pointer += 1
20 right_pointer -= 1
21
22 # Join the character list to form the resulting string and return it.
23 return "".join(char_list)
24
1class Solution {
2 public String makeSmallestPalindrome(String s) {
3 // Convert the input string to a character array for easy manipulation.
4 char[] characters = s.toCharArray();
5
6 // Use two pointers, starting from the beginning and end of the character array.
7 for (int left = 0, right = characters.length - 1; left < right; ++left, --right) {
8 // If the characters at the two pointers don't match, replace both with the smaller one.
9 if (characters[left] != characters[right]) {
10 characters[left] = characters[right] =
11 (characters[left] < characters[right]) ? characters[left] : characters[right];
12 }
13 }
14
15 // Convert the character array back to a string and return.
16 return String.valueOf(characters);
17 }
18}
19
1class Solution {
2public:
3 // Function to create the lexicographically smallest palindrome from a given string
4 string makeSmallestPalindrome(string s) {
5 // Use two pointers, starting from the beginning and end of the string
6 for (int left = 0, right = s.size() - 1; left < right; ++left, --right) {
7 // If the characters at the current left and right positions are different
8 if (s[left] != s[right]) {
9 // Update both characters to the lexicographically smaller one
10 s[left] = s[right] = std::min(s[left], s[right]);
11 }
12 }
13 // Return the modified string which is the smallest palindrome
14 return s;
15 }
16};
17
1function makeSmallestPalindrome(inputString: string): string {
2 // Convert the input string into an array of characters.
3 const charArray = inputString.split('');
4
5 // Iterate over the string from both ends towards the center.
6 for (let leftIndex = 0, rightIndex = inputString.length - 1; leftIndex < rightIndex; ++leftIndex, --rightIndex) {
7
8 // Check if characters at current left and right indexes are different.
9 if (inputString[leftIndex] !== inputString[rightIndex]) {
10 // Choose the lexicographically smaller character among the two
11 // and replace both characters with it to make the string a palindrome.
12 charArray[leftIndex] = charArray[rightIndex] =
13 inputString[leftIndex] < inputString[rightIndex] ?
14 inputString[leftIndex] : inputString[rightIndex];
15 }
16 }
17
18 // Return the modified array as a string.
19 return charArray.join('');
20}
21
Time and Space Complexity
Time Complexity
The given Python function, makeSmallestPalindrome
, primarily consists of a while loop that iterates over the string elements. The i
index starts from the beginning of the string, and the j
index starts from the end, moving towards the center of the string. Since each iteration moves both pointers (i.e., i
and j
), the loop runs for approximately n/2
iterations, where n
is the length of the input string s
. The operations inside the loop (like comparing characters, assigning characters, and incrementing or decrementing pointers) all have a constant time complexity, O(1)
.
Therefore, the time complexity of the function is O(n/2)
, which simplifies to O(n)
since we drop constants when expressing big O notation.
Space Complexity
The space complexity is determined by the additional space used by the function beyond the input itself. Here, a new list cs
of characters is created from the input string s
, which occupies O(n)
space, where n
is the length of the input string. The rest of the variables (i
, j
) use constant space, O(1)
.
Hence, the overall space complexity of the function is O(n)+O(1)
which simplifies to O(n)
, as the linear term dominates over the constant one.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first