#2522

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Partition String Into Substrings With Values at Most K

Determine the minimum number of substrings from a numeric string such that each substring value does not exceed k using dynamic programming.

string dynamic programming greedy

Problem Statement

Given a string s of digits from 1 to 9 and an integer k, partition s into contiguous substrings where each substring represents an integer value less than or equal to k. Return the minimum number of substrings needed for such a valid partition.

If it is impossible to create any valid partition where all substring values are at most k, return -1. Optimize your solution using state transition dynamic programming and consider greedy extensions for efficiency.

Examples

Example 1

Input: s = "165462", k = 60

Output: 4

We can partition the string into substrings "16", "54", "6", and "2". Each substring has a value less than or equal to k = 60. It can be shown that we cannot partition the string into less than 4 substrings.

Example 2

Input: s = "238182", k = 5

Output: -1

There is no good partition for this string.

Constraints

1 <= s.length <= 105
s[i] is a digit from '1' to '9'.
1 <= k <= 109

Solution Approach

Dynamic Programming State Definition

Define dp[i] as the minimum number of substrings to partition s[0..i]. Initialize dp[0] = 0. For each position, check all previous partition points where the substring value does not exceed k and update dp[i] accordingly.

Greedy Substring Extension

While scanning the string, extend the current substring greedily until the numeric value would exceed k. When it exceeds k, commit the previous substring and start a new one. This reduces unnecessary state checks in DP.

Efficient Value Computation

Compute substring integer values incrementally to avoid repeated parsing. Maintain a rolling number using multiplication and addition by digit, and reset when starting a new substring to keep operations within bounds.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) in greedy-enhanced DP, where n is the length of the string, because each character is processed once with constant work per substring check. Space complexity is O(n) for the DP array or O(1) if using only previous state tracking.

What Interviewers Usually Probe

The interviewer may hint at using a DP array to track minimal partitions.
Watch for questions on how to efficiently check substring numeric values against k.
Expect prompts to optimize naive DP using greedy substring extensions.

Common Pitfalls or Variants

Common pitfalls

Attempting to parse entire substrings repeatedly without incremental computation, causing timeouts.
Starting new substrings too early or too late, which can overcount partitions.
Ignoring the case when a single digit exceeds k, leading to incorrect -1 return.

Follow-up variants

Partition string into substrings where each numeric value is at least L and at most K.
Find the maximum number of valid substrings instead of minimum.
Allow substrings to include leading zeros and adjust the value check accordingly.

FAQ

What is the main pattern used in Partition String Into Substrings With Values at Most K?

The problem primarily uses state transition dynamic programming combined with greedy substring extension to minimize the number of partitions.

How do I handle substrings that exceed the value k?

Whenever a substring value exceeds k, commit the previous substring and start a new substring; if a single digit exceeds k, return -1.

Can leading zeros affect the solution?

Since s contains digits 1-9 only, leading zeros do not appear, so the solution does not need to handle them.

What is the optimal way to compute substring values?

Compute values incrementally by multiplying the previous value by 10 and adding the new digit to avoid repeated parsing.

What are common mistakes when applying DP for this problem?

Common mistakes include over-parsing substrings, miscounting partitions, and neglecting the -1 return for impossible cases.

terminal

Solution

Solution 1: Memoization Search

We design a function $dfs(i)$ to represent the minimum number of partitions starting from index $i$ of string $s$. The answer is $dfs(0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        @cache
        def dfs(i):
            if i >= n:
                return 0
            res, v = inf, 0
            for j in range(i, n):
                v = v * 10 + int(s[j])
                if v > k:
                    break
                res = min(res, dfs(j + 1))
            return res + 1

        n = len(s)
        ans = dfs(0)
        return ans if ans < inf else -1

Continue Practicing

#2472 maximum number of non overlapping palindrome substrings #2573 find the string with lcp #2645 minimum additions to make valid string