Problem

A user intended to type a string, but some key presses may have been repeated consecutively. You are given the final typed string typed, which is formed by taking an unknown original string and expanding some characters into one or more consecutive copies.

Your task is to determine how many different original strings could have produced typed under this process.

More precisely, if the original string contains a character c, then in the typed result that character may appear as a contiguous block of one or more c characters. Different original strings are counted as distinct.

Return the number of possible original strings.

Notes

• The original string must be non-empty unless the typed string is empty.
• Characters are compared exactly and only consecutive repetitions are merged into blocks.
• The answer may be large, so use integer arithmetic as needed.

Input Format

• A string typed.

Output Format

• Return an integer: the number of valid original strings that could expand to typed.

Constraints

• 0 <= typed.length
• typed contains lowercase English letters in the most common formulation of this problem.
• The answer fits in a 64-bit signed integer for the intended test data.

Hints

• First compress typed into groups of equal characters.
• Think about how many ways each group can be interpreted as coming from a single original character or multiple repeated presses.
• A dynamic programming count over the compressed groups is often the cleanest approach.