Difficult Problems
InterviewTime limit1sMemory limit512 MB
Given a string of lowercase letters and 'A's, split the 'A's into the maximum number of groups with distinct positive sizes, allowing lowercase letters between groups.
- Level
Medium6 of 10
- Topics
- Greedy, Math, String, Combinatorics
- Solved
- No attempts yet
Problem
Yesterday, for the first time, Tosha took part in a programming contest. But the problems were so difficult that sometimes he wanted to scream. Tosha knew that noise during the contest is prohibited, so he had to scream on paper: he sometimes wrote a few letters "A" on a piece of paper, when he felt that the task was too difficult. The more difficult the problem was, the more letters "A" Tosha wrote down in the process of solving it.
The next day Tosha wanted to boast to his classmates that he had participated in the contest and solved a lot of problems. But he forgot the number of problems and even didn't have the statements to check. Fortunately, Tosha saved his notes, so now he can roughly estimate the number of problems.
He remembers that all the problems had different non-zero difficulty, which means that solving each task he wrote a distinct positive number of letters "A". And these screaming letters conveniently stand out, because there are no other uppercase letters, all other notes he made in lowercase. Note that he could write down some lowercase notes between "A"-s he wrote for the same problem.
Help Tosha to find out what is the maximum number of problems that could have been there in the contest.
Input
Input contains a nonempty string consisting of lowercase English letters and characters "A". The length of does not exceed , it contains at least one "A".
Output
Print one integer --- the maximum number of problems in the contest.