3333. Find the Original Typed String II LeetCode Solution
In this guide, you will get 3333. Find the Original Typed String II LeetCode Solution with the best time and space complexity. The solution to Find the Original Typed String II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Original Typed String II
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 109 + 7.
Example 1:
Input: word = “aabbccdd”, k = 7
Output: 5
Explanation:
The possible strings are: “aabbccdd”, “aabbccd”, “aabbcdd”, “aabccdd”, and “abbccdd”.
Example 2:
Input: word = “aabbccdd”, k = 8
Output: 1
Explanation:
The only possible string is “aabbccdd”.
Example 3:
Input: word = “aaabbb”, k = 3
Output: 8
Constraints:
1 <= word.length <= 5 * 105
word consists only of lowercase English letters.
1 <= k <= 2000
3333. Find the Original Typed String II LeetCode Solution in C++
class Solution {
public:
int possibleStringCount(string word, int k) {
const vector<int> groups = getConsecutiveLetters(word);
const int totalCombinations = accumulate(
groups.begin(), groups.end(), 1L,
[](long subtotal, int group) { return subtotal * group % kMod; });
if (k <= groups.size())
return totalCombinations;
// dp[j] := the number of ways to form strings of length j using
// groups[0..i]
vector<int> dp(k);
dp[0] = 1; // Base case: empty string
for (int i = 0; i < groups.size(); ++i) {
vector<int> newDp(k);
int windowSum = 0;
int group = groups[i];
for (int j = i; j < k; ++j) {
newDp[j] = (newDp[j] + windowSum) % kMod;
windowSum = (windowSum + dp[j]) % kMod;
if (j >= group)
windowSum = (windowSum - dp[j - group] + kMod) % kMod;
}
dp = std::move(newDp);
}
const int invalidCombinations = accumulate(
dp.begin(), dp.end(), 0,
[](int subtotal, int count) { return (subtotal + count) % kMod; });
return (totalCombinations - invalidCombinations + kMod) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns consecutive identical letters in the input string.
// e.g. "aabbbc" -> [2, 3, 1].
vector<int> getConsecutiveLetters(const string& word) {
vector<int> groups;
int group = 1;
for (int i = 1; i < word.length(); ++i)
if (word[i] == word[i - 1]) {
++group;
} else {
groups.push_back(group);
group = 1;
}
groups.push_back(group);
return groups;
}
}; /* code provided by PROGIEZ */
3333. Find the Original Typed String II LeetCode Solution in Java
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 % kMod);
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) % kMod;
windowSum = (windowSum + dp[j]) % kMod;
if (j >= group)
windowSum = (windowSum - dp[j - group] + kMod) % kMod;
}
dp = newDp;
}
final int invalidCombinations = Arrays.stream(dp).reduce(0, (a, b) -> (a + b) % kMod);
return (totalCombinations - invalidCombinations + kMod) % kMod;
}
private static final int kMod = 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;
}
} // code provided by PROGIEZ
3333. Find the Original Typed String II LeetCode Solution in Python
class Solution:
def possibleStringCount(self, word: str, k: int) -> int:
kMod = 1_000_000_007
groups = self._getConsecutiveLetters(word)
totalCombinations = functools.reduce(lambda subtotal, group:
subtotal * group % kMod, groups)
if k <= len(groups):
return totalCombinations
# dp[j] := the number of ways to form strings of length j using groups[0..i]
dp = [0] * k
dp[0] = 1 # Base case: empty string
for i, group in enumerate(groups):
newDp = [0] * k
windowSum = 0
for j in range(i, k):
newDp[j] = (newDp[j] + windowSum) % kMod
windowSum = (windowSum + dp[j]) % kMod
if j >= group:
windowSum = (windowSum - dp[j - group] + kMod) % kMod
dp = newDp
return (totalCombinations - sum(dp)) % kMod
def _getConsecutiveLetters(self, word: str) -> list[int]:
"""
Returns consecutive identical letters in the input string.
e.g. "aabbbc" -> [2, 3, 1].
"""
groups = []
group = 1
for i in range(1, len(word)):
if word[i] == word[i - 1]:
group += 1
else:
groups.append(group)
group = 1
groups.append(group)
return groups # code by PROGIEZ
