ANTIPALINDR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: satyam_343
Tester: udhav2003
Editorialist: iceknight1093

DIFFICULTY:

1488

PREREQUISITES:

None

PROBLEM:

You’re given a string S of length N. In one move, you can replace one of its characters with any other lowercase Latin letter.
Find the minimum number of moves required to make S an anti-palindrome, i.e, no rearrangement of S is a palindrome.

EXPLANATION:

First, let’s check whether S is itself an anti-palindrome, in which case the answer will be 0.

To do this, we need to check whether S can be rearranged into a palindrome.
Checking for this is somewhat well-known, and can be done as follows:

  • If N is even, then S can be rearranged to form a palindrome if and only if every character appears an even number of times.
  • If N is odd, S can be rearranged to form a palindrome if and only if exactly one character appears an odd number of times; and everything else appears an even number of times.
Proof

Let’s prove the even case first. It should be fairly obvious if you think about it a bit.

If S can be rearranged into a palindrome, then every element of S has an opposite ‘pair’ element in this rearrangement.
This means each character appears an even number of times in total, as claimed.

On the other hand, if every character appears an even number of times, we can then pair up copies of the same character and use them to form a palindrome by placing them at opposing sides of the string.

The odd case is similar: there’s a unique ‘middle’ character which accounts for the odd frequency because everything else is paired up; but the proof is otherwise the same.

So, check if S satisfies the respective condition for its parity; if it doesn’t, the answer is of course 0.

What about the case when S does satisfy those conditions, i.e, can be rearranged into a palindrome?

Let’s analyze what we can change.

  • If N is even, we know every character occurs an even number of times.
    just replace any character of S with any other character; and both the new and the old character will now have an odd frequency.
    So, the answer in this case is 1
  • If N is odd, we need slightly more casework.
    Exactly one character has an odd frequency; let it be \alpha. Then,
    • If S has some character that’s not \alpha, then one move is enough.
      Replace a non-\alpha character with another different non-\alpha character, now there are three characters with odd occurrences.
    • If S consists of only the letter \alpha repeated N times, the answer is 2: replacing one occurrence of \alpha with something else isn’t enough (since the new character will have odd frequency but \alpha will be even).
      However, after one replacement we’ll be back in the first case; and from there we know the answer is 1.

Putting it together, we have the following cases:

  • If S is already an anti-palindrome, the answer is 0.
  • Otherwise,
    • If N is even, the answer is 1.
    • If N is odd and S contains at least two distinct characters, the answer is 1.
    • Else, the answer is 2.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Editorialist's code (Python) 
from collections import Counter
for _ in range(int(input())):
    n = int(input())
    s = input()
    freq = Counter(s)
    odds = 0
    for x in freq.values(): odds += x%2
    if n%2 == 0:
        if odds == 0: print(1)
        else: print(0)
    else:
        if len(freq) == 1: print(2)
        elif odds == 1: print(1)
        else: print(0)
1 Like