PDEL - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a string S. In one move, you can delete any substring of S which has length \lt |S| and isn’t a palindrome.
Find the minimum number of moves needed to turn S into a palindrome.

EXPLANATION:

If S is already a palindrome, 0 moves are required.

A length 1 string is always a palindrome, so a couple of simple checks we can make are deleting either the first N-1 characters (to leave only the last character), or the last N-1 characters (to leave only the first character).
If either of these moves are possible (meaning either of those length N-1 substrings is not a palindrome), the answer is 1.

If the answer isn’t 0 or 1, it’s impossible to turn S into a palindrome!

Proof

If the answer isn’t 0 or 1, we know three pieces of information:

  1. S isn’t a palindrome.
  2. The strings S_1S_2\ldots S_{N-1} and S_2S_3\ldots S_N are both palindromes.

The second condition is quite strong, and gives us equality relations between pairs of characters.
Comparing opposite characters in the two palindromes, It can be seen that:

  • S_1 = S_{N-1}
  • S_2 = S_N = S_{N-2}
  • S_3 = S_{N-1} = S_{N-4}
    \vdots

In general, S_1S_2\ldots S_{N-1} being a palindrome tells us that S_i = S_{N-i} for all 1 \leq i \lt N.
Similarly, S_2S_3\ldots S_{N} being a palindrome tells us that S_i = S_{N+2-i} for all 2 \leq i \leq N.

Together, these tell us that S_1=S_3=S_5=\ldots and S_2=S_4=S_6=\ldots
That is, the characters at even indices must all be equal, and the characters at odd indices must all be equal.

But, if this is the case:

  1. If N is odd, the string would be a palindrome, which we know isn’t the case.
    • In fact, you can prove an even stronger condition here: all the characters must be equal.
      Either way, the string would be a palindrome but we’re in the case where it isn’t, so N can’t be odd.
  2. If N is even, the string looks like \texttt{ababab\ldots ab}.
    The only non-palindromic substrings of this are \texttt{abab\ldots ab} or \texttt{baba\ldots ba}.
    • Deleting either of these types of strings will just give us a shorter alternating string instead: in particular, no matter what, the first character will always be \texttt{a} and the last will always be \texttt{b}.
    • The first and last characters not being equal means the resulting string can’t ever be a palindrome.

So, it’s impossible to obtain a palindrome by deletion if more than one move is necessary.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
def ispal(s):
    return s == s[::-1]

for _ in range(int(input())):
    n = int(input())
    s = input()
    
    if ispal(s): print(0)
    elif ispal(s[:n-1]) and ispal(s[1:]): print(-1)
    else: print(1)
2 Likes