[Leetcode] 3333. Find the Original Typed String II (v hard retry)

https://leetcode.com/problems/find-the-original-typed-string-ii/?envType=daily-question&envId=2025-07-02

initial

v hard its building upon the previous substrings so we needa use dp. Initialising dp[0][0] as 1, dp[i][j] is represented as number of valid substrings that used until group[i] and is up till jth character limit. This group is the number of consecutive chars like if string is aabb then groups=[2,2].

when we wanna use the first group (aa), we look at the previous state and if theres not an empty substring (i.e value isnt 0) then we build upon the previous substring to add our current groups' character onto it. So dp[1][1] (using group[1] and using just 1a) is +=dp[0][0] so it consists of a and dp[1][2] (using group[1] and using 2a) is +=dp[0][0] so its substring is aa

now when we use group2, we can use the previous state so dp[2][2]+=dp[1][1] (ab), dp[2][3]+=dp[1][1]+dp[1][2] (abb,aab) dp[2][4]+=dp[1][2] (aabb).

We then use complement maths, at least k = all poss - at most k.

sol

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int:
        groups=[]
        tmp=""
        tmp_count=1
        for c in word:
            if tmp!=c:
                if tmp!="":
                    groups.append(tmp_count)
                tmp=c
                tmp_count=1
            else:
                tmp_count+=1
        groups.append(tmp_count)
        max_length=sum(group for group in groups)
        MOD = 10**9+7
        dp=[[0 for _ in range(k)] for _ in range(len(groups)+1)]
        dp[0][0]=1
        for i in range(len(groups)):
            cur_group=groups[i]
            for length in range(max_length+1):
                if length<k:
                    if dp[i][length]:
                        for j in range(1,cur_group+1):
                            if length+j<k:
                                dp[i+1][length+j] =(dp[i+1][length+j]+ dp[i][length]) %MOD
        all_poss=1
        for group in groups:
            all_poss=(all_poss*group)%MOD
        for j in range(k):
            all_poss-=dp[-1][j]
        return all_poss%MOD

much TLE optimised prefix sol (i dont get)

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int:
        # Parse groups
        groups = []
        count = 1
        for i in range(1, len(word)):
            if word[i] == word[i-1]:
                count += 1
            else:
                groups.append(count)
                count = 1
        groups.append(count)
        
        MOD = 10**9 + 7
        
        # Calculate total possibilities
        total = 1
        for group in groups:
            total = (total * group) % MOD
        
        # If minimum possible length >= k, return total
        if len(groups) >= k:
            return total
        
        # DP with prefix sum optimization
        prev = [0] * k
        prev[0] = 1
        
        for group_size in groups:
            curr = [0] * k
            
            # Build prefix sum array of prev
            prefix = [0] * (k + 1)
            for i in range(k):
                prefix[i + 1] = (prefix[i] + prev[i]) % MOD
            
            for length in range(k):
                # We want sum of prev[max(0, length-group_size)] to prev[length-1]
                left = max(0, length - group_size)
                right = length
                
                # Sum from prev[left] to prev[right-1]
                curr[length] = (prefix[right] - prefix[left] + MOD) % MOD
            
            prev = curr
        
        # Sum all invalid cases (length < k)
        invalid = sum(prev) % MOD
        
        return (total - invalid + MOD) % MOD

complexity

Time Complexity:

O(G × k × max_group_size)
Where G = number of groups, k = minimum length constraint
In worst case: O(n × k × n) = O(n² × k) if all groups have size n

Space Complexity:

O(G × k) for the 2D DP table
Can be optimized to O(k) using rolling arrays