Find the Original Typed String I

Easy
1079.

Find the Original Typed String I

Find the Original Typed String I is an easy coding problem on strings, asked in Amazon, Google and Accenture interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var possibleStringCount = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Original Typed String I — Problem & Solution

Find the Original Typed String I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find the Original Typed String I is an easy coding problem on strings, asked in Amazon, Google and Accenture interviews.

  • 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.

Hints for Find the Original Typed String I

  1. Hint 1

    If the long press happened in a run of length L, the original had that run at any length from 1 to L.

  2. Hint 2

    That is L - 1 shortened possibilities per run, plus the one where nothing was held down.

  3. Hint 3

    Summing L - 1 over every run is the same as counting adjacent equal pairs.

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])

Java

public static int possibleStringCount(String word) {
    int total = 1;
    for (int i = 1; i < word.length(); i++) {
        if (word.charAt(i) == word.charAt(i - 1)) total++;
    }
    return total;
}

C++

int possibleStringCount(string word) {
    int total = 1;
    for (size_t i = 1; i < word.size(); i++) {
        if (word[i] == word[i - 1]) total++;
    }
    return total;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings