We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Original Typed String I

Number: 3617

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Alice is typing a target string but might accidentally press a key too long. When this happens, a letter is output multiple times instead of the intended number. However, such an error occurs on at most one key press throughout the entire string. Given the final displayed string word, determine how many possible original strings Alice might have intended to type.

Key Insights

  • The final string can be divided into groups of consecutive identical characters.
  • For any group with a single character, no error could have occurred.
  • If a group has length L ≥ 2, then an error may have occurred in that group. Specifically, if that group is the one with the error, the intended number of characters could be any value between 1 and L-1.
  • Since at most one error occurred, if an error happens in a group the other groups must be exactly as displayed.
  • Additionally, it’s possible that no error occurred in any group, in which case the intended string is exactly the final string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the word (we scan the string once).
Space Complexity: O(1) (using only a few counters and variables).

Solution

We solve the problem by iterating through the string and grouping consecutive identical characters. For each group:

  • If its length is 1, there is only one possibility (no error).
  • If its length is L (L ≥ 2), then if that group was the error group, the intended count could be any integer from 1 to L-1 (L-1 possibilities), otherwise the group remains as is.

Since the error occurs in at most one group, we can choose one group to “fix” (if eligible) while leaving all others unchanged. Thus, the total possibilities equals: 1 (case when no error occurred in any group) plus the sum of (L-1) for every group with length ≥2.

The algorithm uses a single pass (or a pass over groups) and constant extra space.

Code Solutions

# Python solution with line-by-line comments

def countOriginalStrings(word: str) -> int:
    # Initialize the answer for the case of no error.
    total_possibilities = 1

    # Initialize pointer and length of word.
    n = len(word)
    i = 0

    # Process the string to identify groups of consecutive characters.
    while i < n:
        # Start a group for the current character.
        count = 1
        # Move pointer i+1 until a different character is encountered.
        while i + 1 < n and word[i] == word[i + 1]:
            count += 1
            i += 1
        # If group length is at least 2, it is eligible for an accidental extra press.
        # Original intended group length can be any number from 1 to count-1.
        if count >= 2:
            total_possibilities += (count - 1)
        # Move to the next distinct character.
        i += 1
    return total_possibilities

# Example usage:
print(countOriginalStrings("abbcccc"))  # Expected output: 5
← Back to All Questions