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.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
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**.**

Solution

Method 1 – Two Pointers Greedy

Intuition

To make the string a palindrome with the minimum number of operations, for each pair of characters at symmetric positions, we can replace the larger character with the smaller one. This ensures the palindrome is lexicographically smallest among all possible minimum-operation palindromes.

Approach

  1. Use two pointers, one at the start (l) and one at the end (r) of the string.
  2. For each pair (l, r), if the characters are different, replace the larger one with the smaller.
  3. Move the pointers towards the center.
  4. Return the resulting string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    string makeSmallestPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (s[l] != s[r]) {
                char c = min(s[l], s[r]);
                s[l] = s[r] = c;
            }
            l++; r--;
        }
        return s;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func makeSmallestPalindrome(s string) string {
    b := []byte(s)
    l, r := 0, len(b)-1
    for l < r {
        if b[l] != b[r] {
            c := b[l]
            if b[r] < c { c = b[r] }
            b[l], b[r] = c, c
        }
        l++; r--
    }
    return string(b)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public String makeSmallestPalindrome(String s) {
        char[] arr = s.toCharArray();
        int l = 0, r = arr.length - 1;
        while (l < r) {
            if (arr[l] != arr[r]) {
                char c = (char)Math.min(arr[l], arr[r]);
                arr[l] = arr[r] = c;
            }
            l++; r--;
        }
        return new String(arr);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun makeSmallestPalindrome(s: String): String {
        val arr = s.toCharArray()
        var l = 0; var r = arr.size - 1
        while (l < r) {
            if (arr[l] != arr[r]) {
                val c = minOf(arr[l], arr[r])
                arr[l] = c; arr[r] = c
            }
            l++; r--
        }
        return String(arr)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def makeSmallestPalindrome(self, s: str) -> str:
        arr = list(s)
        l, r = 0, len(arr) - 1
        while l < r:
            if arr[l] != arr[r]:
                c = min(arr[l], arr[r])
                arr[l] = arr[r] = c
            l += 1; r -= 1
        return ''.join(arr)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn make_smallest_palindrome(s: String) -> String {
        let mut arr: Vec<u8> = s.bytes().collect();
        let (mut l, mut r) = (0, arr.len() - 1);
        while l < r {
            if arr[l] != arr[r] {
                let c = arr[l].min(arr[r]);
                arr[l] = c; arr[r] = c;
            }
            l += 1; r -= 1;
        }
        String::from_utf8(arr).unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    makeSmallestPalindrome(s: string): string {
        const arr = s.split('');
        let l = 0, r = arr.length - 1;
        while (l < r) {
            if (arr[l] !== arr[r]) {
                const c = arr[l] < arr[r] ? arr[l] : arr[r];
                arr[l] = arr[r] = c;
            }
            l++; r--;
        }
        return arr.join('');
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s. Each character is checked at most once.
  • 🧺 Space complexity: O(n), for the output string (or array copy).