Number of Beautiful Partitions
01 · Problem
You are given a string s of digits '1' to '9' and two integers k and minLength. Call the digits '2', '3', '5' and '7' prime; every other digit is non-prime.
A partition of s into exactly k non-empty, contiguous, non-overlapping substrings (covering the whole string in order) is beautiful if every substring:
- starts with a prime digit,
- ends with a non-prime digit, and
- has length at least
minLength.
Return the number of beautiful partitions of s, modulo 10^9 + 7. Return 0 if none exist.
02 · Examples
s = "23542185131", k = 3, minLength = 2
3
The beautiful partitions are "2354|218|5131", "2354|21851|31" and "2354218|51|31".
s = "23542185131", k = 3, minLength = 3
1
Only "2354|218|5131" works; every other split has a piece shorter than 3 or a piece with the wrong first/last digit.
s = "3312958", k = 3, minLength = 1
1
The only beautiful partition is "331|29|58".
03 · Constraints
- 011 <= k, minLength <= s.length <= 1000
- 02s consists only of the digits '1' to '9'
- 03Return the answer modulo 109 + 7
04 · Optimal complexity
- Time
- O(n * k)
- Space
- O(n * k)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.