Connection Status:
Competition Arena > PalindromePartition

PalindromePartition

SRM 299 · 2006-04-22 · by Vovka

SRM 299 · 2006-04-22 · by Vovka · Dynamic Programming, String Manipulation
Class Name: PalindromePartition
Return Type: int
Method Name: partition
Arg Types: (vector<string>)
Problem Statement

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.

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

Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PalindromePartition with a public method int partition(vector<string> s) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous