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.
The idea is to partition the string greedily by always taking the longest possible substring that can form according to the constraint (value ≤ k). Start with the first character, keep extending the substring until adding another digit creates a number greater than k. If at any character, the digit itself is already greater than k, return -1, as it's impossible to form a valid substring starting at that position.
We iterate over 's' and at each step, try to form the largest possible substring from the current position that doesn't exceed 'k'. We increment the count for each newly formed substring, and move the index to the start of the next potential substring.
Python
JavaScript
Time Complexity: O(n), where n is the length of the string 's'.
Space Complexity: O(1), since no extra data structures are used apart from variables for counting and indexing.
Use dynamic programming to solve the problem by maintaining a dp array where dp[i] represents the minimum number of partitions required for the substring s[0:i+1]. For each i, attempt substrings ending at i and start with j (where j < i) such that the substring value doesn't exceed k. Transition dp[i] by minimizing over previous positions.
The code initializes a dp array where each position is set to a high number (INT_MAX) except for dp[0], which starts at 0. For each position `i`, it calculates potential substrings that end at `i` by iterating backwards. It updates dp[i] if the current number is within k range and the subproblem dp[j-1] is not overflown. Finally, it checks if dp[n] is valid for a good partition.
Time Complexity: O(n^2), where n is the length of the string due to the nested loop.
Space Complexity: O(n), because of the dp array used for recording minimum partitions until each position.
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).
The calculation process of the function dfs(i) is as follows:
i geq n, it means that it has reached the end of the string, return 0.i. If the value of the substring is less than or equal to k, then we can take the substring as a partition. Then we can get dfs(j + 1), where j is the end index of the substring. We take the minimum value among all possible partitions, add 1, and that is the value of dfs(i).Finally, if dfs(0) = infty, it means there is no good partition, return -1. Otherwise, return dfs(0).
To avoid repeated calculations, we can use memoization search.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the length of the string 's'. |
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the length of the string due to the nested loop. |
| Memoization Search | — |
| 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. |
2522. Partition String Into Substrings With Values at Most K Hindi • ThinkCode • 774 views views
Watch 9 more video solutions →Practice Partition String Into Substrings With Values at Most K with our built-in code editor and test cases.
Practice on FleetCode