HHAL - Editorial

editorial
, , ,
1

Problem link : contest practice

Difficulty : CakeWalk

Pre-requisites : None

Problem :
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.

Explanation

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.

Solutions : setter tester

3 Likes
2

How to solve if the string consists of more than 2 types of characters.

3

Check if the string is palindrome or not. If yes, answer is 1. If no, answer is number of different characters in that string.

4

Let the given array be A

1)for this reverse the given common string

2)Find LCS http://www.geeksforgeeks.org/printing-longest-common-subsequence/

3)Then check the given LCS is palindrome or not

4)if yes

i)destroy common element in array A
say new aaray is A’

ii)Repeat from Step 1 while you sizeof(A’)=0

5)if no

i)Repeat from step 1 to 3

 i)if no then stop array A cant be reduced

if yes
i)repeat step 4
ii)go to step 1

5

worst solution ever

6

@achaitanyasai :
for test case : abcbd , answer is 3 but your solution return 4.