PalindromeSubsequence

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.