3333. Find the Original Typed String II
About this solution
Find the Original Typed String II is a unknown-difficulty LeetCode problem covering the String, Dynamic Programming patterns. The Java solution below uses an idiomatic approach that is clean, readable, and directly submittable on LeetCode. Study the logic carefully — recognising the underlying pattern is the key skill that transfers to similar problems in interviews.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
import java.util.*;
class Solution {
public int possibleStringCount(String word, int k) {
List<Integer> groups = getConsecutiveLetters(word);
final int totalCombinations = (int) groups.stream().mapToLong(Integer::longValue).reduce(1L,
(a, b) -> a * b % MOD);
if (k <= groups.size())
return totalCombinations;
// dp[j] := the number of ways to form strings of length j using
// groups[0..i]
int[] dp = new int[k];
dp[0] = 1; // Base case: empty string
for (int i = 0; i < groups.size(); ++i) {
int[] newDp = new int[k];
int windowSum = 0;
int group = groups.get(i);
for (int j = i; j < k; ++j) {
newDp[j] = (newDp[j] + windowSum) % MOD;
windowSum = (windowSum + dp[j]) % MOD;
if (j >= group)
windowSum = (windowSum - dp[j - group] + MOD) % MOD;
}
dp = newDp;
}
final int invalidCombinations = Arrays.stream(dp).reduce(0, (a, b) -> (a + b) % MOD);
return (totalCombinations - invalidCombinations + MOD) % MOD;
}
private static final int MOD = 1_000_000_007;
// Returns consecutive identical letters in the input string.
// e.g. "aabbbc" -> [2, 3, 1].
private List<Integer> getConsecutiveLetters(final String word) {
List<Integer> groups = new ArrayList<>();
int group = 1;
for (int i = 1; i < word.length(); ++i)
if (word.charAt(i) == word.charAt(i - 1))
++group;
else {
groups.add(group);
group = 1;
}
groups.add(group);
return groups;
}
}