LeetCode Daily Challenge-3333: Find the Original Typed String II - Advanced Dynamic Programming Solution(Hard)

• LeetCode Link
• Date: 2nd July 2025
• Topics: String, Dynamic Programming, Prefix Sum

Problem Understanding

LeetCode 3333 builds upon the simpler "Find the Original Typed String I" problem by adding a crucial constraint: we need to find strings of length at least k. Alice still makes typing mistakes by holding keys too long, but now we have a minimum length requirement that significantly complicates the solution.

Problem Statement

• Input: A string word (Alice's typed output) and integer k (minimum original string length)
• Output: Number of possible original strings of length ≥ k, modulo 10^9 + 7
• Key insight: Every group of repeated characters can be compressed, giving us multiple choices per group

Examples

Input: word = "aabbcc", k = 3
Output: 8
- Total possibilities: 2×2×2 = 8 (each group of 2 gives 2 choices)
- All have length ≥ 3, so answer is 8

Input: word = "aaaa", k = 3  
Output: 3
- Total possibilities: 4 (can choose 1,2,3,4 characters from group)
- Valid lengths ≥ 3: lengths 3,4 → 2 + 1 = 3 ways

The C Solution Deep Dive

Let's analyze the provided C solution step by step:

Step 1: Group Formation

int cnt = 1;
int freq[n];
int freqSize = 0;

for(int i=1; i<n; ++i){
    if (word[i] == word[i-1]) {
        ++cnt;
    } else {
        freq[freqSize++] = cnt;
        cnt = 1;
    }
}
freq[freqSize++] = cnt;

Purpose: Groups consecutive identical characters

• "aabbcc" → freq = [2, 2, 2]
• "aaaa" → freq = [4]

Step 2: Calculate Total Possibilities

long ans = 1;
for (int i=0; i<freqSize; ++i) {
    ans = ans * freq[i] % MOD;
}

Logic: Each group of size g contributes g choices (can take 1 to g characters)

• Total combinations = product of all group sizes

Step 3: Early Return for Simple Cases

if (k <= freqSize) {
    return ans;
}

Optimization: If k ≤ number of groups, every combination is valid since we must take at least 1 character per group.

Step 4: Dynamic Programming for Complex Cases

int dp[k];
memset(dp, 0, sizeof(int)*k);
dp[0] = 1;

for (int i=0; i<freqSize; ++i) {
    // ... sliding window sum technique
}

Core DP Logic: dp[j] = number of ways to form a string of exactly j characters

Algorithm Breakdown: The Sliding Window DP

The most complex part is the DP calculation:

for (int i=0; i<freqSize; ++i) {
    long sum = 0;
    int groupSize = freq[i];
    int newDp[k];
    memset(newDp, 0, sizeof(int)*k);

    for (int j=0; j<k; ++j) {
        if (j>0) {
            sum = (sum + dp[j-1])%MOD;
        }
        if (j > groupSize) {
            sum = (sum - dp[j-groupSize-1] + MOD)%MOD;
        }
        newDp[j] = sum;
    }
    memcpy(dp, newDp, sizeof(dp));
}

What's Happening Here?

1. Prefix Sum Building: sum maintains a running total of recent dp values
2. Sliding Window: We maintain exactly groupSize elements in our sum
3. Transition: For each length j, we consider all ways to add 1 to groupSize characters from current group

Visual Example: "aabb" with k=3

Groups: [2, 2] (aa, bb)
Initial: dp = [1, 0, 0]

After group 1 (aa):
- Can take 1 or 2 'a's
- dp[1] += dp[0] = 1 (take 1 'a')
- dp[2] += dp[0] = 1 (take 2 'a's)
- Result: dp = [0, 1, 1]

After group 2 (bb):
- Can take 1 or 2 'b's from previous states
- dp[2] += dp[1] = 1 (ab)
- dp[3] += dp[1] + dp[2] = 2 (abb, aab)
- Result: dp = [0, 0, 1, 2]

Step 5: Final Calculation

long invalid = 0;
for(int i=0; i<k; i++) {
    invalid = (invalid + dp[i]) % MOD;
}
return (ans-invalid+MOD)%MOD;

Final Formula: Total - Invalid = Valid

• Total: All possible combinations
• Invalid: Combinations with length < k
• Valid: Combinations with length ≥ k

Time and Space Complexity

Time Complexity

• Grouping: O(n) where n = length of word
• DP: O(freqSize × k) where freqSize ≤ n
• Overall: O(n × k)

Space Complexity

• DP arrays: O(k)
• Frequency array: O(n)
• Overall: O(n + k)

Key Optimizations in This Solution

1. Sliding Window Sum

Instead of recalculating sums repeatedly, we maintain a running sum and slide the window:

sum = (sum + dp[j-1])%MOD;           // Add new element
sum = (sum - dp[j-groupSize-1] + MOD)%MOD; // Remove old element

2. Memory Management

memcpy(dp, newDp, sizeof(dp)); // Efficient array copying

3. Modular Arithmetic

Consistent use of MOD operations prevents integer overflow.

Alternative Approaches

Recursive with Memoization

int dfs(int groupIndex, int remainingLength, int memo[][]) {
    if (groupIndex == freqSize) {
        return remainingLength <= 0 ? 1 : 0;
    }

    if (memo[groupIndex][remainingLength] != -1) {
        return memo[groupIndex][remainingLength];
    }

    int result = 0;
    for (int take = 1; take <= freq[groupIndex]; take++) {
        result = (result + dfs(groupIndex + 1, remainingLength - take, memo)) % MOD;
    }

    return memo[groupIndex][remainingLength] = result;
}

Space-Optimized DP

Since we only need the previous row, we can use rolling arrays to reduce space complexity to O(k).

Common Pitfalls and Debug Tips

1. Modular Arithmetic Errors

// Wrong: can become negative
sum = (sum - dp[j-groupSize-1]) % MOD;

// Correct: handle negative values
sum = (sum - dp[j-groupSize-1] + MOD) % MOD;

2. Array Bounds

// Always check bounds before accessing
if (j > groupSize) {
    sum = (sum - dp[j-groupSize-1] + MOD) % MOD;
}

3. Memory Initialization

memset(dp, 0, sizeof(int)*k);  // Initialize to 0
memset(newDp, 0, sizeof(int)*k);  // Don't forget temporary arrays

Testing Strategy

void test_solution() {
    // Test cases
    assert(possibleStringCount("aabbcc", 3) == 8);
    assert(possibleStringCount("aaaa", 3) == 3);
    assert(possibleStringCount("abcd", 4) == 1);

    // Edge cases
    assert(possibleStringCount("a", 1) == 1);
    assert(possibleStringCount("aa", 1) == 2);
    assert(possibleStringCount("aa", 3) == 0);  // Impossible case
}

Conclusion

LeetCode 3333 is an elegant combination of combinatorics and dynamic programming, requiring:

1. Pattern Recognition: Identify consecutive character groups
2. Combinatorial Thinking: Calculate total possibilities
3. Dynamic Programming: Handle the minimum length constraint
4. Optimization: Use sliding window techniques for efficiency

The solution demonstrates how adding a simple constraint (minimum length) can transform a trivial counting problem into a complex DP challenge. The key insight is using complementary counting: calculate total possibilities, then subtract invalid cases.

Key Takeaway: When dealing with constrained counting problems, consider the "Total - Invalid = Valid" approach combined with efficient DP techniques.