2569. Number of Beautiful Partitions

class Solution:
    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
        MOD = 10**9 + 7
        n = len(s)
        primes = {'2', '3', '5', '7'}
        
        # Check if valid partition is possible
        if s[0] not in primes or s[-1] in primes:
            return 0
        
        # Find valid partition points (where we can start a new partition)
        # A valid point i means s[i] is prime and s[i-1] is not prime
        valid = [False] * (n + 1)
        for i in range(minLength, n + 1):
            if s[i - 1] not in primes and (i == n or s[i] in primes):
                valid[i] = True
        
        # DP: dp[i][j] = number of ways to partition s[0:i] into j parts
        # Optimize space: only need previous row
        
        # dp[j] = number of ways to partition ending at some position into j parts
        dp = [0] * (k + 1)
        dp[0] = 1
        
        # Prefix sum for optimization
        for part in range(1, k + 1):
            new_dp = [0] * (k + 1)
            prefix = 0
            j = 0
            for i in range(minLength, n + 1):
                # Add contribution from position (i - minLength) if it was valid for (part-1) parts
                while j <= i - minLength:
                    if j == 0 or valid[j]:
                        prefix = (prefix + dp[part - 1]) if j == 0 else prefix
                    j += 1
                # Actually we need to reconsider the DP formulation
                pass
            dp = new_dp
        
        # Simpler DP approach
        # dp[i][j] = ways to partition s[0:i] into j parts where s[0:i] is valid ending
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        
        for j in range(1, k + 1):
            prefix = 0
            for i in range(j * minLength, n + 1):
                # Can we end partition j at position i?
                if i == n or (s[i - 1] not in primes and s[i] in primes):
                    # Sum all dp[prev][j-1] where prev <= i - minLength and prev is valid start for part j
                    pass
        
        # Let's use cleaner DP
        # dp[j] at position i = ways to have j partitions ending at i
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        
        for j in range(1, k + 1):
            psum = 0
            for i in range(minLength, n + 1):
                # Update prefix sum: add dp[i-minLength][j-1] if that position is valid end for part j-1
                prev = i - minLength
                if prev == 0 or (s[prev-1] not in primes and s[prev] in primes):
                    psum = (psum + dp[prev][j-1]) % MOD
                
                # Can we end part j at position i?
                if i == n or (s[i-1] not in primes and s[i] in primes):
                    dp[i][j] = psum
        
        return dp[n][k]