PalindromeSubsequence | Topcoder Archive

Problem Statement

A palindrome is a string that is identical to its reverse. For example, "a", "abba", "aaaaa", and "abbabba" are all palindromes.

A subsequence of a string s is any string of the form s[i₁]s[i₂]...s[i_k] such that the sequence of indices is strictly increasing. (Formally, 0 <= i₁ < i₂ ... < i_k <= |s|-1.)

For example, the strings "", "b", "ace", and "abcde" are all subsequences of the string "abcde", but the strings "bb" and "cba" are not subsequences of "abcde".

A partition of a string s is a set of subsequences that is constructed in such a way that each index into s is used for exactly one of the subsequences.

For example, let s = "aaabb". Then:

{"aaabb"} is a valid partition of s.
{"ab", "aab"} is a valid partition of s.
{"a", "b", "a", "b", "a"} is a valid partition of s.
{"ab", "abb"} is not a valid partition of s because you would have to use some 'b' multiple times.
{"ba", "aab"} is not a valid partition of s because "ba" is not a subsequence of s.
{"a", "a", "b", "b"} is not a valid partition of s because some letter of s remained unused.

The size of a partition is the number of strings it contains. For example, the size of {"aaabb"} is 1, the size of {"ab", "aab"} is 2, and the size of {"a", "ab", "ab"} is 3.

You are given a String s. Each character in s is either 'a' or 'b'. Find a partition of s such that:

Each string in the partition is a palindrome.
The size of the partition is as small as possible.

Suppose that you found a solution that uses k subsequences. Number those subsequences from 1 to k in any order. Return a int[] with |s| elements. For each valid i, element i of your return value should be the number of the subsequence that contains the character at index i in the string s. (See the examples for a clarification.)

If there are multiple optimal solutions, you may return any of them.

Definition

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

Constraints

s will contain between 1 and 50 characters, inclusive.
Every character of s will be either 'a' or 'b'.

Examples

```
"bababba"
```
```
Returns: {1, 2, 2, 1, 2, 1, 2 }
```
Here, it is obvious that there is no valid partition of size 1. There are multiple valid partitions of size 2. The sample output describes one of them, as follows: string s = b a b a b b a return value = 1 2 2 1 2 1 2 ------------------------------ subsequence 1 = b a b subsequence 2 = a b b a In other words, we partitioned the string "bababba" into {"bab", "abba"}. Both "bab" and "abba" are palindromes, so this is a valid solution.
```
"abba"
```
```
Returns: {1, 1, 1, 1 }
```
Here the input is already palindrome, thus the optimum is 1.
```
"b"
```
```
Returns: {1 }
```
```
"babb"
```
```
Returns: {1, 1, 1, 2 }
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.