Number of beautiful partitions

String Dynamic Programming Prefix Sum

32.8% acceptance

Feb 25, 2026

371

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 ('2','3','5','7') and ends with a non-prime digit. Return the number of beautiful partitions of s modulo 10^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn beautiful_partitions(s: String, k: i32, min_length: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let s = s.as_bytes();
    let n = s.len();
    let k = k as usize;
    let m = min_length as usize;

    fn is_prime(c: u8) -> bool { matches!(c, b'2' | b'3' | b'5' | b'7') }

    if !is_prime(s[0]) || is_prime(s[n - 1]) { return 0; }

    // dp[i] = # beautiful partitions of s[0..i] into `part` parts (1-indexed end)
    // Base: 0 parts, dp[0] = 1
    let mut prev = vec![0i64; n + 1];
    prev[0] = 1;

    for _ in 0..k {
      let mut curr = vec![0i64; n + 1];
      let mut prefix = 0i64;
      for i in 0..=n {
        // Add new l = i - m to prefix if valid (s[l] is prime start)
        if i >= m {
          let l = i - m;
          // l < n always holds since i <= n and m >= 1
          if is_prime(s[l]) {
            prefix = (prefix + prev[l]) % MOD;
          }
        }
        // curr[i] = prefix if s[i-1] is non-prime end
        if i > 0 && !is_prime(s[i - 1]) {
          curr[i] = prefix;
        }
      }
      prev = curr;
    }
    prev[n] as i32
  }
}