A boutique theatre's cloakroom logs every coat action in the exact order it happens. Each character of the log is either A, meaning a guest hands over a coat to be hung on a fresh peg, or D, meaning a guest reclaims a coat and frees up its peg. The theatre wants to buy pegs exactly once, before doors open, in a quantity that will never run short no matter how the night unfolds. Given the full log, find the smallest number of pegs that guarantees every A in the log always finds an empty peg waiting for it.
You may assume the log is consistent: at every prefix of the log, the number of D characters seen so far never exceeds the number of A characters seen so far (nobody reclaims a coat that was never hung).
s of length n made only of the characters A and D.s consists only of the characters A and Ds has at most as many D characters as A charactersExample 1
Input
AADDA
Expected
2
Explanation
Track coats on pegs after each character: A->1, A->2, D->1, D->0, A->1. The busiest moment needs 2 pegs, so the answer is 2.
Example 2
Input
ADAD
Expected
1
Explanation
After each character the count goes A->1, D->0, A->1, D->0. At most 1 coat is ever hanging at once, so 1 peg suffices.
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 →