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 II

Difficulty: Hard

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. You are given a string word, which represents the final output displayed on Alice's screen. You are also given a positive integer k. Return the total number of possible original strings that Alice might have intended to type, if she was trying to type a string of size at least k. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • Each character in the string can appear multiple times due to prolonged key presses.
  • We need to consider the minimum length of the original string that Alice may have intended, which is k.
  • The number of combinations of original strings depends on the frequency of each character in the string.
  • We can use dynamic programming to count the valid combinations of characters while ensuring the length constraint.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string word.
Space Complexity: O(1) since we are using a fixed amount of space for counters.

Solution

To solve this problem, we will use a dynamic programming approach. We will iterate through the given string word and keep track of consecutive characters. For each segment of the same character, we will calculate the number of ways to reduce its count to form the original string. Specifically, we will maintain a running total of possible lengths for segments of characters, ensuring that the total length meets the minimum requirement of k. The combination counts can be computed using the formula for combinations from combinatorial mathematics.

Code Solutions

def countOriginalStrings(word, k):
    MOD = 10**9 + 7
    dp = [0] * (len(word) + 1)
    dp[0] = 1  # Base case: 1 way to form an empty string
    total_length = 0
    
    i = 0
    while i < len(word):
        char = word[i]
        count = 0
        
        # Count consecutive characters
        while i < len(word) and word[i] == char:
            count += 1
            i += 1
        
        # Update dp array for this character segment
        for j in range(total_length, -1, -1):
            for l in range(1, count + 1):
                if j + l <= len(word):
                    dp[j + l] = (dp[j + l] + dp[j]) % MOD
        
        total_length += count
    
    # Calculate the number of valid strings of length at least k
    result = sum(dp[k:total_length + 1]) % MOD
    return result
← Back to All Questions