Problem link : contest practice Difficulty : CakeWalk Prerequisites : 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. ExplanationHow to get 30 pointsSince 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 pointsIf 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.
This question is marked "community wiki".
asked 31 Aug '14, 14:06

How to solve if the string consists of more than 2 types of characters. answered 06 Sep '14, 13:54
Check if the string is palindrome or not. If yes, answer is 1. If no, answer is number of different characters in that string.
(06 Sep '14, 15:08)
Let the given array be A 1)for this reverse the given common string 2)Find LCS http://www.geeksforgeeks.org/printinglongestcommonsubsequence/ 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
if yes i)repeat step 4 ii)go to step 1
(15 Sep '14, 21:34)
worst solution ever
(15 Sep '14, 22:10)
@achaitanyasai : for test case : abcbd , answer is 3 but your solution return 4.
(21 Sep '14, 13:37)
