A packaging-line conveyor is fitted with a strip of directional tags, one per crate slot. Each tag is either 'F' (the crate at that slot gets nudged one slot forward) or 'B' (nudged one slot back). Across the entire strip the number of 'F' tags equals the number of 'B' tags, so a crate ridden from the very first slot to the very last would end up back where it started. A technician wants to cut the strip into the largest possible number of contiguous pieces such that every piece, read on its own, is itself balanced -- containing an equal number of 'F' and 'B' tags -- and such that the pieces, placed back-to-back in their original order, reproduce the strip exactly. Determine the maximum number of pieces achievable.
Example 1
Input
FBFFBBFBFB
Expected
4
Explanation
Scanning left to right and tracking the running difference between the F-count and B-count, the balance after each character is 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, which returns to zero at positions 2, 6, 8, and 10. This splits the strip into 4 balanced pieces: "FB", "FFBB", "FB", "FB".
Example 2
Input
FBBBBFFFBF
Expected
3
Explanation
Tracking the running balance across "FBBBBFFFBF" gives 1,0,-1,-2,-3,-2,-1,0,-1,0, which touches zero at positions 2, 8, and 10, so the strip splits into exactly 3 balanced pieces: "FB", "BBBFFF", "BF".
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 →