Scale Engineer

Number of Beautiful Partitions

Hard
#2261Time: O(n * k * n). There are `n * k` states, and each state computation involves a loop that can run up to `n` times.Space: O(n * k) for the memoization table and recursion stack depth.
Patterns
Dynamic Programming
Data structures
String

Prompt

You are given a string s that consists of the digits '1' to '9' and two integers k and minLength.

A partition of s is called beautiful if:

  • s is partitioned into k non-intersecting substrings.
  • Each substring has a length of at least minLength.
  • Each substring starts with a prime digit and ends with a non-prime digit. Prime digits are '2', '3', '5', and '7', and the rest of the digits are non-prime.

Return the number of beautiful partitions of s. Since the answer may be very large, return it modulo 109 + 7.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: s = "23542185131", k = 3, minLength = 2
Output: 3
Explanation: There exists three ways to create a beautiful partition:
"2354 | 218 | 5131"
"2354 | 21851 | 31"
"2354218 | 51 | 31"

Example 2:

Input: s = "23542185131", k = 3, minLength = 3
Output: 1
Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".

Example 3:

Input: s = "3312958", k = 3, minLength = 1
Output: 1
Explanation: There exists one way to create a beautiful partition: "331 | 29 | 58".

 

Constraints:

  • 1 <= k, minLength <= s.length <= 1000
  • s consists of the digits '1' to '9'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses recursion with memoization, which is a top-down dynamic programming technique. We define a function that solves the problem for a subproblem and use a memoization table to store the results of subproblems to avoid redundant calculations. The state of our recursion is defined by (i, j), representing the starting index of the string suffix to be partitioned and the number of partitions remaining.

Algorithm

  1. Define a recursive function solve(i, j) that computes the number of beautiful partitions for the suffix of the string s starting at index i, using j partitions.
  2. Base Cases:
    • If j is 0, it means we have used all k partitions. A valid solution is found only if we have also consumed the entire string (i == n). So, return 1 if i == n, otherwise 0.
    • If i >= n (we've run out of string) but j > 0 (still need to make partitions), it's impossible. Return 0.
  3. Recursive Step:
    • For a partition to start at index i, s.charAt(i) must be a prime digit. If not, no beautiful partition can start here, so return 0.
    • If s.charAt(i) is prime, iterate through all possible end positions p for the current partition. The end position p must satisfy:
      • The partition length p - i + 1 is at least minLength.
      • The character s.charAt(p) is a non-prime digit.
    • For each valid end position p, we have formed one beautiful partition s.substring(i, p + 1). We then need to partition the rest of the string s.substring(p + 1) into j - 1 partitions. The number of ways to do this is given by the recursive call solve(p + 1, j - 1).
    • Sum up the results from these recursive calls, taking the result modulo 10^9 + 7.
  4. Memoization:
    • To avoid recomputing results for the same state (i, j), use a 2D array memo[n][k+1] to store the computed values. Before computing solve(i, j), check if it's already in the memoization table.

Walkthrough

The core idea is to define a function, say solve(i, j), which calculates the number of ways to partition the suffix s[i:] into j beautiful partitions. The final answer is solve(0, k).

To compute solve(i, j), we try to form the first of the j partitions. This partition must start at index i and end at some index p. For this partition s[i...p] to be beautiful, it must satisfy three conditions: its length must be at least minLength, s[i] must be prime, and s[p] must be non-prime. If s[i] is not prime, solve(i, j) is 0. Otherwise, we iterate through all valid p and for each, we recursively call solve(p + 1, j - 1) to find the number of ways for the rest of the string. The sum of results from these calls gives solve(i, j).

Without memoization, this would lead to an exponential number of calls. By storing the result of each solve(i, j) call in a 2D array memo, we ensure that each subproblem is solved only once.

class Solution {    int n;    int k;    int minLength;    String s;    int MOD = 1_000_000_007;    Integer[][] memo;     private boolean isPrime(char c) {        return c == '2' || c == '3' || c == '5' || c == '7';    }     private int solve(int i, int j) {        if (j == 0) {            return i == n ? 1 : 0;        }        if (i >= n) {            return 0;        }        if (memo[i][j] != null) {            return memo[i][j];        }         // The first character of a partition must be prime.        if (!isPrime(s.charAt(i))) {            return memo[i][j] = 0;        }         long count = 0;        // Iterate through possible end points 'p' for the current partition.        for (int p = i + minLength - 1; p < n; p++) {            // The last character of a partition must be non-prime.            if (!isPrime(s.charAt(p))) {                count = (count + solve(p + 1, j - 1)) % MOD;            }        }         return memo[i][j] = (int) count;    }     public int beautifulPartitions(String s, int k, int minLength) {        this.n = s.length();        this.k = k;        this.minLength = minLength;        this.s = s;        this.memo = new Integer[n + 1][k + 1];                if (!isPrime(s.charAt(0)) || isPrime(s.charAt(n - 1))) {            return 0;        }         return solve(0, k);    }}

Complexity

Time

O(n * k * n). There are `n * k` states, and each state computation involves a loop that can run up to `n` times.

Space

O(n * k) for the memoization table and recursion stack depth.

Trade-offs

Pros

  • Relatively straightforward to formulate from the problem's recursive nature.

  • Correctly solves the problem for smaller constraints.

Cons

  • The time complexity of O(n^2 * k) is too slow for the given constraints (n, k <= 1000) and will result in a Time Limit Exceeded (TLE) error.

Solutions

class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int beautifulPartitions ( String s , int k , int minLength ) { int n = s . length (); if (! prime ( s . charAt ( 0 )) || prime ( s . charAt ( n - 1 ))) { return 0 ; } int [][] f = new int [ n + 1 ][ k + 1 ]; int [][] g = new int [ n + 1 ][ k + 1 ]; f [ 0 ][ 0 ] = 1 ; g [ 0 ][ 0 ] = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { if ( i >= minLength && ! prime ( s . charAt ( i - 1 )) && ( i == n || prime ( s . charAt ( i )))) { for ( int j = 1 ; j <= k ; ++ j ) { f [ i ][ j ] = g [ i - minLength ][ j - 1 ]; } } for ( int j = 0 ; j <= k ; ++ j ) { g [ i ][ j ] = ( g [ i - 1 ][ j ] + f [ i ][ j ]) % MOD ; } } return f [ n ][ k ]; } private boolean prime ( char c ) { return c == '2' || c == '3' || c == '5' || c == '7' ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem