Welcome to Subscribe On Youtube
2697. Lexicographically Smallest Palindrome
Description
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 <= 1000
s
consists of only lowercase English letters.
Solutions
Solution 1: Greedy + Two Pointers
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.

class Solution { public String makeSmallestPalindrome(String s) { char[] cs = s.toCharArray(); for (int i = 0, j = cs.length  1; i < j; ++i, j) { if (cs[i] != cs[j]) { cs[i] = cs[j] = cs[i] < cs[j] ? cs[i] : cs[j]; } } return String.valueOf(cs); } }

class Solution { public: string makeSmallestPalindrome(string s) { for (int i = 0, j = s.size()  1; i < j; ++i, j) { if (s[i] != s[j]) { s[i] = s[j] = s[i] < s[j] ? s[i] : s[j]; } } return s; } };

class Solution: def makeSmallestPalindrome(self, s: str) > str: i, j = 0, len(s)  1 cs = list(s) while i < j: if s[i] != s[j]: cs[i] = cs[j] = min(s[i], s[j]) i, j = i + 1, j  1 return "".join(cs)

func makeSmallestPalindrome(s string) string { cs := []byte(s) for i, j := 0, len(s)1; i < j; i, j = i+1, j1 { if cs[i] != cs[j] { if cs[i] < cs[j] { cs[j] = cs[i] } else { cs[i] = cs[j] } } } return string(cs) }

function makeSmallestPalindrome(s: string): string { const cs = s.split(''); for (let i = 0, j = s.length  1; i < j; ++i, j) { if (s[i] !== s[j]) { cs[i] = cs[j] = s[i] < s[j] ? s[i] : s[j]; } } return cs.join(''); }

impl Solution { pub fn make_smallest_palindrome(s: String) > String { let mut b: Vec<u8> = s.bytes().collect(); let mut i = 0; let mut j = b.len()  1; while i < j { if b[i] != b[j] { if b[i] < b[j] { b[j] = b[i]; } else { b[i] = b[j]; } } i += 1; j = 1; } String::from_utf8(b).unwrap() } }