Watch 10 video solutions for Partition String Into Substrings With Values at Most K, a medium level problem involving String, Dynamic Programming, Greedy. This walkthrough by ThinkCode has 774 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s consisting of digits from 1 to 9 and an integer k.
A partition of a string s is called good if:
s is part of exactly one substring.k.Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1.
Note that:
"123" is 123 and the value of "1" is 1.
Example 1:
Input: s = "165462", k = 60 Output: 4 Explanation: 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 Explanation: There is no good partition for this string.
Constraints:
1 <= s.length <= 105s[i] is a digit from '1' to '9'.1 <= k <= 109
Problem Overview: You are given a numeric string s and an integer k. Split the string into the minimum number of contiguous substrings such that every substring, when interpreted as an integer, is less than or equal to k. If any single digit already exceeds k, the partition is impossible.
Approach 1: Greedy Expansion (O(n) time, O(1) space)
The optimal strategy is greedy. Scan the string from left to right and build the current number digit by digit. Each step multiplies the current value by 10 and adds the next digit. If the value becomes greater than k, you start a new partition at that digit and reset the current value. This works because extending a substring as long as it stays ≤ k always minimizes the total number of partitions. The algorithm performs a single pass over the string, making it linear time. This approach relies on simple numeric accumulation and is a classic greedy pattern often seen in Greedy and String problems.
Approach 2: Dynamic Programming (O(n * d) time, O(n) space)
A Dynamic Programming solution considers all valid substring endings. Let dp[i] represent the minimum partitions needed for the prefix ending at index i. For each index, expand backward while constructing the numeric value of s[j..i]. If the value is ≤ k, update dp[i] = min(dp[i], dp[j-1] + 1). The backward expansion stops once the number exceeds k. Since the number of digits in k limits the substring length, each state checks only a small window of characters. This approach is more flexible if the problem later introduces additional constraints or scoring rules.
Recommended for interviews: The greedy scan is the expected solution. It runs in O(n) time with constant space and demonstrates that you recognize the monotonic property of the substring value as digits are appended. Showing the DP formulation first can demonstrate deeper reasoning, but implementing the greedy approach proves you can simplify the problem to its optimal form.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Expansion | O(n) | O(1) | Best choice for the original problem. Single pass with minimal memory. |
| Dynamic Programming | O(n * d) | O(n) | Useful when exploring variations or when greedy correctness is unclear. |