408510: GYM103176 C camelCaseCounting

Camel case is one of the common practices for naming variables in programming, so that phrases, clauses (or even sentences) can be represented as a string with no spaces or punctuation. In camel case, the first letter of each word (except the first word) is written in capital letter. All other letters, including the first letter of the first word, should be written in lower case. For instance, the phrase "camel case" in camel case is camelCase, and "to do list" in camel case is toDoList. Here are some other examples of valid camel case writing:

• laSalleCollege ("la salle college")
• puiChing ("pui ching")
• challenge ("challenge")
• oMG ("o m g")

And here are some examples of invalid camel case writing:

• ProgrammingChallenge
• ILoveCoding
• THISproblemISeasy
• TLDR

Given a valid camel case writing $$$S$$$, please find the number of unique substrings that is a valid camel case writing. Here, substring is a contiguous sequence of characters within a string.

The only line contains a string $$$S$$$, which consists of only lowercase letters and uppercase letters. It is guaranteed that $$$S$$$ is a valid camel case writing, and $$$1\le |S|\le 10^6$$$ (where $$$|S|$$$ is the length of $$$S$$$).

Output a single integer, the number of unique substrings that is a valid camel case writing.

ease

9

camelCaseCounting

130

oMG

3

In Sample 1, the 9 unique substrings that are valid camel case writings: a, e, s, as, ea, se, ase, eas, ease.

In Sample 2, several substrings of valid camel case writings: elCaseCount, aseCou, cam, e.