Skip to content

3088. Make String Anti-palindrome

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  string makeAntiPalindrome(string s) {
    const int n = s.length();
    int i = n / 2;
    ranges::sort(s);
    if (s[i] != s[n - 1 - i])
      return s;

    int j = getFirstDiffIndexInSecondHalf(s);
    while (s[i] == s[n - 1 - i]) {
      if (j == n)
        return "-1";
      swap(s[i++], s[j++]);
    }

    return s;
  }

 private:
  // Returns the first index in s[n / 2..n) that is different from the first
  // letter of the second half, s[n / 2].
  int getFirstDiffIndexInSecondHalf(const string& s) {
    const int n = s.size();
    const char firstLetter = s[n / 2];
    int firstDiffIndex = n / 2;
    while (firstDiffIndex < n && s[firstDiffIndex] == firstLetter)
      ++firstDiffIndex;
    return firstDiffIndex;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public String makeAntiPalindrome(String s) {
    final int n = s.length();
    int i = n / 2;
    char[] chars = s.toCharArray();
    Arrays.sort(chars);
    if (chars[i] != chars[n - 1 - i])
      return new String(chars);

    int j = getFirstDiffIndexInSecondHalf(chars);
    while (chars[i] == chars[n - 1 - i]) {
      if (j == n)
        return "-1";
      final char temp = chars[i];
      chars[i] = chars[j];
      chars[j] = temp;
      ++i;
      ++j;
    }

    return new String(chars);
  }

  // Returns the first index in chars[n / 2..n) that is different from the first
  // letter of the second half, chars[n / 2].
  private int getFirstDiffIndexInSecondHalf(char[] chars) {
    final int n = chars.length;
    final char firstLetter = chars[n / 2];
    int firstDiffIndex = n / 2;
    while (firstDiffIndex < n && chars[firstDiffIndex] == firstLetter)
      ++firstDiffIndex;
    return firstDiffIndex;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def makeAntiPalindrome(self, s: str) -> str:
    n = len(s)
    i = n // 2
    chars = sorted(list(s))
    if chars[i] != chars[n - 1 - i]:
      return ''.join(chars)

    j = self._getFirstDiffIndexInSecondHalf(chars)
    while chars[i] == chars[n - 1 - i]:
      if j == n:
        return '-1'
      chars[i], chars[j] = chars[j], chars[i]
      i += 1
      j += 1

    return ''.join(chars)

  def _getFirstDiffIndexInSecondHalf(self, chars: list[str]) -> int:
    """
    Returns the first index in chars[n / 2..n) that is different from the first
    letter of the second half, chars[n / 2].
    """
    n = len(chars)
    firstLetter = chars[n // 2]
    firstDiffIndex = n // 2
    while firstDiffIndex < n and chars[firstDiffIndex] == firstLetter:
      firstDiffIndex += 1
    return firstDiffIndex