Welcome to Subscribe On Youtube

3088. Make String Anti-palindrome

Description

We call a string s of even length n an anti-palindrome if for each index 0 <= i < n, s[i] != s[n - i - 1].

Given a string s, your task is to make s an anti-palindrome by doing any number of operations (including zero).

In one operation, you can select two characters from s and swap them.

Return the resulting string. If multiple strings meet the conditions, return the lexicographically smallest one. If it can't be made into an anti-palindrome, return "-1".

 

Example 1:

Input: s = "abca"

Output: "aabc"

Explanation:

"aabc" is an anti-palindrome string since s[0] != s[3] and s[1] != s[2]. Also, it is a rearrangement of "abca".

Example 2:

Input: s = "abba"

Output: "aabb"

Explanation:

"aabb" is an anti-palindrome string since s[0] != s[3] and s[1] != s[2]. Also, it is a rearrangement of "abba".

Example 3:

Input: s = "cccd"

Output: "-1"

Explanation:

You can see that no matter how you rearrange the characters of "cccd", either s[0] == s[3] or s[1] == s[2]. So it can not form an anti-palindrome string.

 

Constraints:

• 2 <= s.length <= 105
• s.length % 2 == 0
• s consists only of lowercase English letters.

Solutions

Solution 1: Greedy + Sorting

The problem asks us to transform the string $s$ into the lexicographically smallest non-palindrome string. We might as well sort the string $s$ first.

Next, we only need to compare whether the two middle characters $s[m]$ and $s[m-1]$ are equal. If they are equal, we find the first character $s[i]$ in the second half that is not equal to $s[m]$, use a pointer $j$ to point to $m$, and then swap $s[i]$ and $s[j]$. If we can’t find such a character $s[i]$, it means that the string $s$ cannot be transformed into a non-palindrome string, return "1". Otherwise, perform the swap operation, move $i$ and $j$ to the right, compare whether $s[j]$ and $s[n-j-1]$ are equal, if they are equal, continue to perform the swap operation until $i$ exceeds the length of the string.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public String makeAntiPalindrome(String s) {
          char[] cs = s.toCharArray();
          Arrays.sort(cs);
          int n = cs.length;
          int m = n / 2;
          if (cs[m] == cs[m - 1]) {
              int i = m;
              while (i < n && cs[i] == cs[i - 1]) {
                  ++i;
              }
              for (int j = m; j < n && cs[j] == cs[n - j - 1]; ++i, ++j) {
                  if (i >= n) {
                      return "-1";
                  }
                  char t = cs[i];
                  cs[i] = cs[j];
                  cs[j] = t;
              }
          }
          return new String(cs);
      }
  }
  

• class Solution {
  public:
      string makeAntiPalindrome(string s) {
          sort(s.begin(), s.end());
          int n = s.length();
          int m = n / 2;
          if (s[m] == s[m - 1]) {
              int i = m;
              while (i < n && s[i] == s[i - 1]) {
                  ++i;
              }
              for (int j = m; j < n && s[j] == s[n - j - 1]; ++i, ++j) {
                  if (i >= n) {
                      return "-1";
                  }
                  swap(s[i], s[j]);
              }
          }
          return s;
      }
  };
  

• class Solution:
      def makeAntiPalindrome(self, s: str) -> str:
          cs = sorted(s)
          n = len(cs)
          m = n // 2
          if cs[m] == cs[m - 1]:
              i = m
              while i < n and cs[i] == cs[i - 1]:
                  i += 1
              j = m
              while j < n and cs[j] == cs[n - j - 1]:
                  if i >= n:
                      return "-1"
                  cs[i], cs[j] = cs[j], cs[i]
                  i, j = i + 1, j + 1
          return "".join(cs)
  
  

• func makeAntiPalindrome(s string) string {
  	cs := []byte(s)
  	sort.Slice(cs, func(i, j int) bool { return cs[i] < cs[j] })
  	n := len(cs)
  	m := n / 2
  	if cs[m] == cs[m-1] {
  		i := m
  		for i < n && cs[i] == cs[i-1] {
  			i++
  		}
  		for j := m; j < n && cs[j] == cs[n-j-1]; i, j = i+1, j+1 {
  			if i >= n {
  				return "-1"
  			}
  			cs[i], cs[j] = cs[j], cs[i]
  		}
  	}
  	return string(cs)
  }
  

• function makeAntiPalindrome(s: string): string {
      const cs: string[] = s.split('').sort();
      const n: number = cs.length;
      const m = n >> 1;
      if (cs[m] === cs[m - 1]) {
          let i = m;
          for (; i < n && cs[i] === cs[i - 1]; i++);
          for (let j = m; j < n && cs[j] === cs[n - j - 1]; ++i, ++j) {
              if (i >= n) {
                  return '-1';
              }
              [cs[j], cs[i]] = [cs[i], cs[j]];
          }
      }
      return cs.join('');
  }
  
  

All Problems

All Solutions