Recover the original string length from a typed string where some characters may have been repeated while typing.
Problem
A user intended to type an original string, but while typing, some key presses may have been repeated consecutively. You are given the final typed string. Determine the original string according to the problem's rules.
For this problem, the key idea is to analyze consecutive runs of equal characters and infer how the typed string could have been produced from the original string.
Task
Given the typed string, return the original string or the required property of the original string as defined by the problem.
Notes
- Consecutive equal characters form a run.
- The answer depends on how repeated typing is interpreted by the problem statement.
- A straightforward scan over the string is typically sufficient.
Input Format
- A single string
srepresenting the typed string. - The exact interpretation of repeated characters follows the problem's typing rules.
Output Format
- Return the value required by the problem statement for the original typed string.
- In most cases, this is computed by scanning consecutive character runs.
Constraints
1 <= s.length <= $10^{5}$is a safe interview-scale assumption for this type of problem.scontains lowercase English letters unless otherwise stated.- Solve in linear or near-linear time.
Example 1
Input
s = "abbccc"
Output
"abc"
Explanation
If repeated adjacent typing is collapsed into a single character, each run contributes one character to the original string.
Example 2
Input
s = "a"
Output
"a"
Explanation
A single character remains unchanged.
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.