Girl Friend and String Gift
All submissions for this problem are available.
Read problems statements in Russian here
Chef's Girl Friend has given him a unique gift. She has given him a string S. Chef being a gentleman wants to return her gift in a unique way. He wants to break the string he has received into some number of substrings so that each substring is a palindrome. However he does not want break the string into too many substrings, otherwise the average size of his strings will become small. What is the minimum number of substrings in which the given string can be broken so that each substring is a palindrome.
Refer http://en.wikipedia.org/wiki/Palindrome for the definition of a "palindrome"
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
- The first line of each test case contains a single integer N denoting the number of alphabets in the given string. The second line contains the given string.
For each test case output a single integer the answer to the given test case. Print answer for each test case on a separate line.
All characters in the given string are upper case English alphabets.
- 1 ≤ T ≤ 10
- 1 ≤ |S| ≤ 5000
1 7 ABCCBDA
Example case 1. The given string can be broken into "A" , "BCCB" , "D" , "A". It can be verified that you can't break the given string into less than 4 substrings such that each substring in a palindrome.
Subtask 1: (15 points):
- 1 ≤ |S| ≤ 20
Subtask 2: (25 points):
- 1 ≤ |S| ≤ 250
Subtask 1: (60 points):
- 1 ≤ |S| ≤ 5000
|Tags||dynamic, ltime05, palindromes, programming, simple, strings, vineetpaliwal|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.