A line of n rivets runs along an assembly line, numbered 1 to n from left to right. Each rivet is currently either loose, marked 'L', or already secure, marked 'S'. In a single operation, the riveting tool clamps down on any three consecutive rivets on the line and secures all three at once (a rivet that was already secure simply stays secure). Determine the minimum number of operations needed to make every rivet on the line secure.
A single line containing the string s of length n, made up only of the characters 'L' and 'S'.
A single integer: the minimum number of clamp operations needed to secure every rivet.
Example 1
Input
LLSLL
Expected
2
Explanation
Clamping rivets 1 through 3 secures the loose rivet at position 1 (rivet 3 is already secure). Clamping rivets 3 through 5 then secures the loose rivets at positions 4 and 5. Two operations suffice, and a single operation cannot reach both loose groups since they are more than two positions apart.
Example 2
Input
LLLLLL
Expected
2
Explanation
All six rivets are loose. Clamping rivets 1 through 3 secures the first three, and clamping rivets 4 through 6 secures the rest, for two operations total; no single operation can secure more than three rivets.
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 →