Number of Beautiful Partitions - Practice Coding Problems

Number of Beautiful Partitions - Problem

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 10⁹ + 7.

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

Input & Output

Example 1 — Basic Case

$ Input: s = "23331", k = 2, minLength = 1

› Output: 1

💡 Note: Only one beautiful partition: ["233", "31"]. "233" starts with prime '2' and ends with non-prime '3'. "31" starts with prime '3' and ends with non-prime '1'.

Example 2 — No Valid Partition

$ Input: s = "23", k = 3, minLength = 1

› Output: 0

💡 Note: Cannot partition string of length 2 into 3 parts, so answer is 0.

Example 3 — Multiple Ways

$ Input: s = "3213", k = 2, minLength = 1

› Output: 2

💡 Note: Two beautiful partitions: ["321", "3"] and ["32", "13"]. Both satisfy the prime start and non-prime end constraints.

Constraints

1 ≤ k ≤ min(s.length, 100)
1 ≤ minLength ≤ s.length
1 ≤ s.length ≤ 1000
s consists of digits '1' through '9'

Visualization

Tap to expand

Understanding the Visualization

Input

String "23331" with k=2, minLength=1

Constraints

Each part starts with prime (2,3,5,7) and ends with non-prime (1,4,6,8,9)

Output

Count of valid partitions: 1

Key Takeaway

🎯 Key Insight: Use DP to count valid ways, checking prime/non-prime constraints for each substring

Asked in

G Google 15 F Facebook 12 a Amazon 8

The key insight is to use dynamic programming to count valid partitions systematically. We define states as (position, remaining_partitions) and build the solution by trying all valid cuts. Best approach uses memoization with O(n²k) time and O(nk) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n² × k)	O(n × k)	Cache results of subproblems to avoid recomputation
Brute Force Recursion	O(2^n)	O(n)	Try all possible ways to partition the string recursively
Bottom-Up Dynamic Programming	O(n² × k)	O(n × k)	Build solution iteratively using 2D DP table

Dynamic Programming with Memoization — Algorithm Steps

Step 1: Create memo table for (position, k) states
Step 2: For each state, try all valid cuts and sum results
Step 3: Return cached result if already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate result for (position, remaining) state

Cache

Store result in memo table

Reuse

Return cached result when same state appears

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int MOD = 1000000007;
const int MAXN = 1005;
int memo[MAXN][105];
int visited[MAXN][105];

int isPrime(char c) {
    return c == '2' || c == '3' || c == '5' || c == '7';
}

int isNonPrime(char c) {
    return c == '1' || c == '4' || c == '6' || c == '8' || c == '9';
}

int dp(char* s, int pos, int remaining, int minLength, int n) {
    if (remaining == 0) {
        return pos == n ? 1 : 0;
    }
    if (pos >= n) {
        return 0;
    }
    
    if (visited[pos][remaining]) {
        return memo[pos][remaining];
    }
    
    long long count = 0;
    for (int end = pos + minLength - 1; end < n; end++) {
        if (isPrime(s[pos]) && isNonPrime(s[end])) {
            count = (count + dp(s, end + 1, remaining - 1, minLength, n)) % MOD;
        }
    }
    
    visited[pos][remaining] = 1;
    memo[pos][remaining] = count;
    return count;
}

int solution(char* s, int k, int minLength) {
    int n = strlen(s);
    memset(visited, 0, sizeof(visited));
    return dp(s, 0, k, minLength, n);
}

int main() {
    char s[1001];
    int k, minLength;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    scanf("%d", &k);
    scanf("%d", &minLength);
    
    int result = solution(s, k, minLength);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × k)

We have n×k states and for each state we try O(n) cuts

⚠ Quadratic Growth

Space Complexity

O(n × k)

Memoization table stores results for n×k states plus recursion stack

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler