Difficulty : CakeWalk
Pre-requisites : None
You have a string H consisting only of ‘a’ and ‘b’. In one move you can remove one palindromic subsequence of string H. Find minimum number of moves to make H empty.
How to get 30 points
Since string is already a palindrome, we can choose whole string in one move(whole string is still a subsequence of the string) and make it zero. So answer is 1.
How to get 100 points
If string is palindrome, we know answer is 1.
If string is not palindrome, then you can notice that string will consist characters ‘a’ and ‘b’ both. We will choose a subsequence such that all ‘a’ are present in it. This subsequence is a palindrome. What will be left after removal of all ‘a’ will be all ‘b’. In next move, we choose whole string. So we can do it in 2 moves.