Find the Original Typed String II - Practice Coding Problems

Find the Original Typed String II - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: word = "aabbcc", k = 4

› Output: 7

💡 Note: Groups are [2,2,2]. We can shorten each group to length 1 or 2. Valid combinations with length ≥ 4: (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2) = 7 ways

Example 2 — Minimum Length

$ Input: word = "aa", k = 1

› Output: 2

💡 Note: Group is [2]. We can shorten to length 1 or 2. Both meet k=1 requirement, so 2 ways total

Example 3 — High Requirement

$ Input: word = "aab", k = 5

› Output: 0

💡 Note: Groups are [2,1]. Maximum possible length is 2+1=3, which is less than k=5, so 0 ways

Constraints

1 ≤ word.length ≤ 2000
word consists of lowercase English letters
1 ≤ k ≤ 2000

Visualization

Tap to expand

Understanding the Visualization

Input

word = "aabbcc", k = 4 (need length ≥ 4)

Process

Group consecutive chars: [aa][bb][cc], try shortening each

Output

Count valid combinations: 7 ways

Key Takeaway

🎯 Key Insight: Each group of consecutive identical characters can be shortened to any length from 1 to its original size

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to group consecutive identical characters and count ways to shorten each group while maintaining minimum length k. Best approach uses dynamic programming to efficiently count valid combinations. Time: O(n × k × max_group), Space: O(n × k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^n)	O(n)	Try all possible ways to shorten consecutive character groups
Bottom-Up Dynamic Programming	O(n × k × max_group_size)	O(n × k)	Build solution iteratively using 2D DP table
Dynamic Programming with Memoization	O(n × k × max_group_size)	O(n × k)	Cache results to avoid redundant calculations

Brute Force Recursion — Algorithm Steps

Identify groups of consecutive identical characters
For each group, try all possible shortened lengths
Recursively count combinations that meet length requirement

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Groups

Find consecutive character groups

Try Lengths

For each group, try all possible shortened lengths

Count Valid

Count combinations with total length ≥ k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int backtrack(int* groups, int groupCount, int idx, int currentLength, int k) {
    if (idx == groupCount) {
        return currentLength >= k ? 1 : 0;
    }
    
    long long count = 0;
    // Try all possible lengths for current group (at least 1)
    for (int length = 1; length <= groups[idx]; length++) {
        count = (count + backtrack(groups, groupCount, idx + 1, currentLength + length, k)) % MOD;
    }
    
    return count;
}

int solution(char* word, int k) {
    int len = strlen(word);
    int groups[1000];
    int groupCount = 0;
    
    // Find groups of consecutive characters
    int i = 0;
    while (i < len) {
        int j = i;
        while (j < len && word[j] == word[i]) {
            j++;
        }
        groups[groupCount++] = j - i;
        i = j;
    }
    
    return backtrack(groups, groupCount, 0, 0, k);
}

int main() {
    char word[1001];
    int k;
    
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(word, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each group can be shortened in multiple ways, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth proportional to number of groups

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler