Question

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:
  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)

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;
  }
};

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

function makeSmallestPalindrome(s: string): string {
  const cs = s.split('');
  for (let i = 0, j = s.length - 1; i < j; ++i, --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 cs: Vec<char> = s.chars().collect();
    let n = cs.len();
    for i in 0..n / 2 {
      let j = n - 1 - i;
      cs[i] = std::cmp::min(cs[i], cs[j]);
      cs[j] = cs[i];
    }
    cs.into_iter().collect()
  }
}