Get started

Find the Original Typed String I — Easy Problem & Solution

A typist may have held one key down too long, repeating a single character extra times — but this happened at most once in the whole word.

  • Difficulty: Easy
  • Topics: Strings
  • Asked at: Amazon, Google, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A typist may have held one key down too long, repeating a single character extra times — but this happened at most once in the whole word.

Given the string word that appeared on screen, return the number of strings that could have been intended.

Example 1

Input: word = "abbcccc"
Output: 5
Explanation: The word itself, plus `abcccc`, `abbccc`, `abbcc` and `abbc`.

Example 2

Input: word = "abcd"
Output: 1
Explanation: Nothing repeats, so nothing was held down.

Example 3

Input: word = "aaaa"
Output: 4
Explanation: The original could have been 1, 2, 3 or 4 `a`s.

Constraints

  • 1 <= word.length <= 100
  • word consists of lowercase English letters.

How to solve Find the Original Typed String I

Exactly one run may have been stretched. A run of length L yields L - 1 shorter originals, and one more possibility covers "no long press at all". Summing L - 1 across the runs is precisely the number of adjacent equal character pairs.

Approach

  1. Start the count at 1 — the word as typed.
  2. Add one for each index where the character equals its predecessor.

Why it works

The "at most once" clause is what makes the runs independent rather than multiplicative: you pick one run and one shortened length, so the possibilities add rather than multiply. Counting adjacent equal pairs is the same sum written without ever identifying the run boundaries.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Adding 1 for the untouched word is easy to forget, and it is always a possibility.
  • The runs add, not multiply — only one key was held.
  • A run of length 1 contributes nothing.

Reference solution

Python

def possibleStringCount(word: str) -> int:
    return 1 + sum(1 for i in range(1, len(word)) if word[i] == word[i - 1])

JavaScript

var possibleStringCount = function(word) {
    var total = 1;
    for (var i = 1; i < word.length; i++) {
        if (word.charAt(i) === word.charAt(i - 1)) total++;
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue