Count how many original strings could have produced a given typed string after accidental repeated keystrokes.
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.lengthtypedcontains 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
typedinto 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.
Input Format
- One string:
typed.
The string represents the final result after some characters may have been repeated consecutively.
Output Format
- A single integer representing the number of possible original strings.
Constraints
- Characters are treated case-sensitively if uppercase appears.
- Repetitions can only occur within the same contiguous block of equal characters.
- Use 64-bit integer arithmetic if the count can be large.
Example 1
Input
typed = "abbccc"
Output
12
Explanation
The string can be viewed as runs: a, bb, ccc. Each run may have come from 1 up to its length repeated presses, contributing multiple possible original forms. The total number of original strings is the product of the choices across runs, minus invalid interpretations that would break the run structure.
Example 2
Input
typed = "aaaa"
Output
4
Explanation
The possible original strings are a, aa, aaa, and aaaa.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.