3330. Find the Original Typed String I


  • Alice is attempting to type a specific string on her computer. However, she tends to be clumsy and may press a key for too long, resulting in a character being typed multiple times.
  • Although Alice tried to focus on her typing, she is aware that she may still have done this at most once.
  • You are given a string word, which represents the final output displayed on Alice’s screen.
  • Return the total number of possible original strings that Alice might have intended to type.

Example 1

Input: word = "abbcccc"

Output: 5

Explanation:

The possible strings are: "abbcccc", "abbccc", "abbcc", "abbc", and "abcccc".

Example 2

Input: word = "abcd"

Output: 1

Explanation:

The only possible string is "abcd".

Example 3

Input: word = "aaaa"

Output: 4

Method 1

【O(n) time | O(1) space】
package Leetcode.String;

/**
 * @Author zhengxingxing
 * @Date 2025/07/01
 */
public class FindTheOriginalTypedStringI {

    public static int possibleStringCount(String word) {
        // Initialize the count to 1.
        // This is because the original string itself (with no long press at all) is always a valid possibility.
        int count = 1;

        // Start from the second character and iterate through the string.
        // We are looking for all pairs of adjacent, identical characters.
        // Each such pair represents a possible place where a "long press" could have occurred.
        for (int i = 1; i < word.length(); i++) {
            // If the current character is the same as the previous one,
            // it means there is a sequence of repeated characters.
            // Each such pair gives us one more possible original string,
            // because we could "remove" one of these repeated characters (simulating that the long press happened here).
            if (word.charAt(i) == word.charAt(i - 1)) {
                count++;
            }
        }

        // Return the total count.
        // This includes:
        //   - The original string itself (no long press)
        //   - One for each possible pair of adjacent identical characters (where a long press could have happened)
        return count;
    }

    public static void main(String[] args) {
        System.out.println(possibleStringCount("abbcccc")); // Output: 5

        System.out.println(possibleStringCount("abcd"));    // Output: 1

        System.out.println(possibleStringCount("aaaa"));    // Output: 4
    }
}




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Algorithm of Rate Limiter
  • 594. Longest Harmonious Subsequence
  • 130. Surrounded Regions
  • 1254. Number of Closed Islands
  • 2684. Maximum Number of Moves in a Grid