A quality-control wire on an assembly line holds a row of beads, each colored with one of at most two possible colors, encoded as lowercase English letters. In a single clearing pass, a technician may pull off any subsequence of beads (not necessarily consecutive along the wire) whose colors read the same forwards and backwards -- that is, any palindromic subsequence -- leaving the remaining beads in their original relative order. Determine the minimum number of passes needed to remove every bead from the wire.
A single line containing the string s (1 <= |s| <= 1000), consisting only of lowercase English letters and using at most two distinct letters overall.
A single integer: the minimum number of passes required to remove all beads from the wire.
1 <= |s| <= 1000s consists of at most two distinct lowercase English letters.Example 1
Input
bbab
Expected
2
Explanation
s = "bbab" is not itself a palindrome (reversed it reads "babb"), so a single pass cannot clear the whole wire. But in the first pass the technician can pull off every 'a' bead (here just the one 'a', which trivially reads the same forwards and backwards), and in the second pass pull off every remaining 'b' bead (also trivially a palindrome, since a run of one repeated letter always is). Two passes suffice and one pass does not, so the answer is 2.
Example 2
Input
aaaa
Expected
1
Explanation
Every bead on the wire is the same color, so the string "aaaa" already reads the same forwards and backwards -- it is itself a palindrome -- and the technician can pull the whole thing off in a single pass. The answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →