×

HHAL - Editorial

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

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

 0 How to solve if the string consists of more than 2 types of characters. answered 06 Sep '14, 13:54 1●3 accept rate: 0% 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 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 (15 Sep '14, 21:34) nil963★ 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)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,639
×1,646
×935
×9

question asked: 31 Aug '14, 14:06

question was seen: 4,091 times

last updated: 21 Sep '14, 13:37