LPALIN - Editorial

editorial
,
1

PROBLEM LINK:

Practice

Contest

Author: Anurag Anand

Tester: Vaibhav Gosain

DIFFICULTY:

CAKEWALK.

PREREQUISITES:

Ad Hoc

PROBLEM:

Given a string, find the minimum number of substrings to remove such that after all the removals, the string is a palindrome.

QUICK EXPLANATION:

The answer is always 0 or 1.

EXPLANATION:

There are two cases:

  • The string is already a palindrome - In this case the answer is 0
  • The string is not a palindrome - In this we can remove all the characters except the first character. So, the remaining string has a single character and hence is a palindrome. Hence, in this case, the answer is 1.

AUTHOR’S SOLUTION:

Author’s solution can be found here.