Find the Original Typed String II | LeetCode 3333 - Python

[prashant]

Wonderful explanation through a dry run. I have rarely seen someone explaining a DP problem through an example. Keep it up!

[candyyy_]

The dry run explanation was so great!!Thank uu!!

[omerabbas]

how did you come up with the dynamic recursion formula for the dynamic programming part? Did you see it before

[swastiktiwari]

Since in any iteration we need only two rows (current row and previous row), we don't need to maintain entire dp table of size (len(groups) + 1)*k. We need to maintain just 2 rows each of size k. Furthermore, we can also avoid creating prefixSum array (and associated space and time) by calculating the needed sum on the fly.

Python 3:

class Solution:
def possibleStringCount(self, word: str, k: int) -> int:
res = cnt = 1
MOD = 10**9 + 7
groups = []
for i in range(1, len(word)):
if word[i] == word[i-1]: cnt+=1
else:
groups.append(cnt)
res = (res * cnt)%MOD
cnt = 1
groups.append(cnt)
res = (res * cnt)%MOD
if k<=len(groups): return res

prev = [0]*k
prev[0] = 1

for i in range(1, len(groups)+1):
curr = [0]*k
currSum = 0
for j in range(1, k):
currSum = (currSum + if j-1-groups[i-1]>=0 else 0))%MOD
curr[j] = currSum
prev = curr

prevSum = 0
for num in prev: prevSum = (prevSum + num)%MOD
return (res - prevSum + MOD)%MOD

[osamadeb-]

First I watched the tabulation part then I derived the recursive approach. But wonderful explanation🐎

[AJ-jqhm]

Man this question was so annoying. I was able to come up with the way that we can simply calculate total possible strings and subtract strings of length strictly less than length k from that, and we get our answer.
So I took a 2d dp array where the row index signifies the current segment index, and column index signifies the length of the string.
dp[number of segments] [k].
I then wrote a recursive + memoized solution to calculate this, where ultimately dp[0][0] would contain my answer.
def f(list, idx, len, k, dp):
if len >=k :
return 0
if idx == len(list) :
if len < k :
return 1
else:
return 0
if dp[idx] [len] >=0 :
return dp[idx] [len]
total = 0
for i in range 1, list[idx]+1:
total += f(list, idx+1, len + i, k) %mod
dp[idx] [len] = total
return total

This worked for 830 cases but beyond that got TLE.

It's so annoying dude.. Like who can come up with an optimized 1D iterative dp solution on the spot?