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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Original Typed String I

Difficulty: Easy

Problem Description

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.

Key Insights

  • Alice can type a character multiple times, but at most once for any character.
  • Each group of consecutive identical characters can contribute to multiple original strings by reducing the count of that character.
  • The number of possible original strings can be calculated based on the lengths of these groups of characters.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string word.
Space Complexity: O(1), as we are using a constant amount of space regardless of the input size.

Solution

To solve this problem, we can use a two-pointer approach to iterate through the string and identify groups of consecutive identical characters. For each group, we can calculate the number of possible original strings by considering how many times we can reduce the character count (from its original count down to 1). The total number of combinations will be the product of the possible counts for each group.

  1. Initialize a count to track the number of possible original strings starting from 1 (the original string itself).
  2. Traverse the string to identify groups of consecutive characters.
  3. For each group, calculate the number of ways to reduce the group size and multiply this with the total count.
  4. Return the final count.

Code Solutions

def countOriginalStrings(word):
    count = 1  # Start with the original string itself
    n = len(word)
    
    i = 0
    while i < n:
        j = i
        # Count the number of consecutive characters
        while j < n and word[j] == word[i]:
            j += 1
        
        # Calculate number of possible reductions for this group
        group_size = j - i
        count += group_size - 1  # We can reduce it from group_size to 1
        
        # Move to the next group
        i = j
    
    return count
← Back to All Questions