You are not logged in. Please login at www.codechef.com to post your questions!

×

HHAL - Editorial

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

This question is marked "community wiki".

asked 31 Aug '14, 14:06

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 31 Aug '14, 14:06


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

link

answered 06 Sep '14, 13:54

shimanshu's gravatar image

2★shimanshu
13
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) achaitanyasai5★

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

(15 Sep '14, 21:34) nil963★

worst solution ever

(15 Sep '14, 22:10) alexvaleanu4★

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

(21 Sep '14, 13:37) shimanshu2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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