### Problem Statement

A palindrome partition is the partitioning of a string such that each separate substring is a palindrome.

For example, the string "ABACABA" could be partitioned in several different ways, such as {"A","B","A","C","A","B","A"}, {"A","BACAB","A"}, {"ABA","C","ABA"}, or {"ABACABA"}, among others.

You are given a String[] s. s is split for convenience only, so you should concatenate all of its elements in order and treat it as a single string.

Return the minimum possible number of substrings in a palindrome partition of s.

### Definition

 Class: PalindromePartition Method: partition Parameters: String[] Returns: int Method signature: int partition(String[] s) (be sure your method is public)

### Constraints

-s will contain between 1 and 50 elements, inclusive.
-Each element of s will contain between 1 and 50 characters, inclusive.
-Every character in every element of s will be an uppercase letter ('A'-'Z').

### Examples

0)

 `{"AAAA"}`
`Returns: 1`
 The string is already a palindrome.
1)

 `{"ABCDEFGH"}`
`Returns: 8`
 No palindrome of length greater than 1 can be obtained from a string where all the characters are different.In this case the palindrome partition consists of substrings that are each one character long: {"A","B","C","D","E","F","G","H"}
2)

 `{"QWERTY","TREWQWERT"}`
`Returns: 5`
 The best partition would be {"QWERTYTREWQ","W","E","R","T"}
3)

 `{"BBCDDECAECBDABADDCEBACCCBDCAABDBADD"}`
`Returns: 22`
4)

 ```{"GKTQWLBWOGQCGERTMYHENNMGUNCAIRFDTPGZFRSHTEAKUGBAIJ", "BLMJJGQYQRRSASFRMRDCUSEVUJYUXGQEZKRLGKVCGFAFVGGPFA", "TRRCIACXCMLWOUHJNZSKXYCBPUMNLMEMWBGWTWBAKUBWICDQCB", "SMLRETHSDQQSYGWOOXERMRLXRPFZMPBINEFSFPOAHGQXXSTHBP", "HYDRLSLYQSDKSHTRZRYBJNVMLVGBZBQVZKPZHUVGDQUKXCMNQL", "UMKPXWCNCNUKJWFAGKKMUHHMWSCPYTGADEXMBLSGJIXOUNZYJS", "UWLIUAUPILVXVTDKQBETPLVPSMSZMQBTBQKEKJTCFXEYPCULBZ", "MSZVBLBVJAXRGFLJNYAUSJZBHIUVAODPOUJGNZNBFUOWTVSEBK", "PVPNMRYZVVNXNYHYGXOHGFFZXHFGHBQPFFCOEEDHEHWRJVYMFB", "HJYENRLFBEEPCGBWVNAUGCJPKYMRDHAHQGXMRMTCREYEUJIZDJ", "PKATAIKXGVURLLNXAKQMOSDXTWHNKYICFSOAYIYOQCELIKPGVY", "QEPXOVKMNUSILPOZFEYPZZEFYVTMIEKVGOVWSOFNWOUZLUBJVZ", "YKGECOBOSBCQKLKDFYINFGXWGYDMSPLPAFKCDEVVLUDKEZKUUS", "YFXORCWLCPCFNSFSXTPYYIENMINHWYSAYCMELEKBVVJKXLUWAZ", "MIKDHLAEYYTMIVOMQLYLUJQAHERLBSYSIPNXGTMRNGITXKVVSN", "FUAJSWGDITKRQVFSBRPAKPXGIOYESLRFOKEEZCDRRYIHYBXKYZ", "YAHPHSREYWYPZBREMDIJOXYZKIOHSBRVCQKJPATIPIDQVISHFV", "MIQRPJIVZFNUWRUDTNEKGHOSSSVAYMSBXPCMMCWZPQXKRNBXKP", "DTERSIZDKVFWNVATGPVNXFQDXNMSVOCGBRXRZSCAIENECIAIBZ", "EPLGCMGLAEGXMYENDYHQZOEEJLFCZVZIJPLXYHFCJGNABFHIYN", "WDMVASMIOSUUFCSLDIWDQFBTZEDNUXTZUJHYNJYUACGQJKTJSU", "MPBHUYYXXISSHJLTXYYLHLMJXUTBJDOWFFNLSPZWJAQYQEDZQW", "EXGGAWFQHRWABGJMSNIYQAKYTOGJKWTSROARTBLOMNVRUZZYWD"}```
`Returns: 1013`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6043

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9820&pm=6043

Vovka

#### Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

#### Problem categories:

Dynamic Programming, String Manipulation