Partition String Into Substrings With Values at Most K solution and explanation
9 more videos on this problem
2522. Partition String Into Substrings With Values at Most K HindiThinkCode · 7:46 · 781 views
Weekly Contest 326 | Partition String Into Substrings With Values at Most KcodingMohan · 11:24 · 560 views
Partition String Into Substrings With Values at Most K | leetcode Weekly 326 | Leetcode MediumBinaryMagic · 13:35 · 429 views
Leetcode Weekly contest 326 - Medium - Partition String Into Substrings With Values at Most KPrakhar Agrawal · 6:35 · 386 views
【每日一题】LeetCode 2522. Partition String Into Substrings With Values at Most KHuifeng Guan · 14:14 · 293 views
2522. Partition String Into Substrings With Values at Most K (Leetcode Medium)Programming Live with Larry · 11:14 · 247 views
2522. Partition String Into Substrings With Values at Most K | LeetCode | C++Deep Tech · 10:56 · 175 views
Leetcode 2522: Partition String Into Substrings With Values at Most KAlgorithms Casts · 12:23 · 171 views
Partition String Into Substrings With Values at Most K || LeetCode weekly 326 || Medium || C++Priyanshi Porwal · 15:59 · 149 views
2522. String Into Substrings With Values at Most K | Weekly Contest 326 | LeetCode | DCC NIT-ADCC NITA · 10:35 · 110 views
The problem
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:
- Each digit of
sis part of exactly one substring. - The value of each substring is less than or equal to
k.
Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1.
Note that:
- The value of a string is its result when interpreted as an integer. For example, the value of
"123"is123and the value of"1"is1. - A substring is a contiguous sequence of characters within a string.
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
Approach overview
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 1: Greedy Approach
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.
def min_partitions(s: str, k: int) -> int:
count = 0
i = 0
while i < len(s):
if int(s[i]) > k:
return -1
current_value = 0
j = i
while j < len(s) and current_value * 10 + int(s[j]) <= k:
current_value = current_value * 10 + int(s[j])
j += 1
count += 1
i = j
return countfunction minPartitions(s, k) {
let count = 0;
let i = 0;
while (i < s.length) {
if (parseInt(s[i]) > k) return -1;
let currentValue = 0;
let j = i;
while (j < s.length && currentValue * 10 + parseInt(s[j]) <= k) {
currentValue = currentValue * 10 + parseInt(s[j]);
j++;
}
count++;
i = j;
}
return count;
}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.
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.
Approach 2: Dynamic Programming Approach
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.
#include <vector>
#include <string>
#include <climits>
using namespace std;
int minPartitions(const string &s, int k) {
int n = s.length();
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0; // no partitions needed for an empty string
for (int i = 1; i <= n; ++i) {
long long num = 0;
for (int j = i; j > 0 && num <= k; --j) {
num = num / 10 + (s[j - 1] - '0') * (long long)pow(10, i - j);
if (num <= k && dp[j - 1] != INT_MAX) {
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
}
return dp[n] == INT_MAX ? -1 : dp[n];
}using System;
public class Solution {
public int MinPartitions(string s, int k) {
var dp = new int[s.Length + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
for (int i = 1; i <= s.Length; i++) {
long num = 0;
for (int j = i; j > 0 && num <= k; j--) {
num = num / 10 + (s[j - 1] - '0') * (long)Math.Pow(10, i - j);
if (num <= k && dp[j - 1] != int.MaxValue) {
dp[i] = Math.Min(dp[i], dp[j - 1] + 1);
}
}
}
return dp[s.Length] == int.MaxValue ? -1 : dp[s.Length];
}
}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.
Approach 3: 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).
The calculation process of the function dfs(i) is as follows:
- If
i geq n, it means that it has reached the end of the string, return0. - Otherwise, we enumerate all substrings starting from
i. If the value of the substring is less than or equal tok, then we can take the substring as a partition. Then we can getdfs(j + 1), wherejis the end index of the substring. We take the minimum value among all possible partitions, add1, and that is the value ofdfs(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.
class Solution {
private Integer[] f;
private int n;
private String s;
private int k;
private int inf = 1 << 30;
public int minimumPartition(String s, int k) {
n = s.length();
f = new Integer[n];
this.s = s;
this.k = k;
int ans = dfs(0);
return ans < inf ? ans : -1;
}
private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] != null) {
return f[i];
}
int res = inf;
long v = 0;
for (int j = i; j < n; ++j) {
v = v * 10 + (s.charAt(j) - '0');
if (v > k) {
break;
}
res = Math.min(res, dfs(j + 1));
}
return f[i] = res + 1;
}
}func minimumPartition(s string, k int) int {
n := len(s)
f := make([]int, n)
const inf int = 1 << 30
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] > 0 {
return f[i]
}
res, v := inf, 0
for j := i; j < n; j++ {
v = v*10 + int(s[j]-'0')
if v > k {
break
}
res = min(res, dfs(j+1))
}
f[i] = res + 1
return f[i]
}
ans := dfs(0)
if ans < inf {
return ans
}
return -1
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Partition String Into Substrings With Values at Most K easy or hard?
The problem is classified as Medium on LeetCode. The implementation is straightforward once the greedy insight is recognized, but identifying that extending the substring as long as it stays ≤ k minimizes partitions requires algorithmic intuition.
Partition String Into Substrings With Values at Most K Python/Java solution
Most implementations follow the same greedy logic across languages. Maintain a running number, append digits while the value stays ≤ k, and split when it exceeds k. The approach works efficiently in Python, JavaScript, C++, or C# with linear time complexity.
How to solve Partition String Into Substrings With Values at Most K in O(n)?
Scan the string from left to right and keep building the current number using current = current * 10 + digit. If the value exceeds k, increment the partition count and start a new substring from the current digit. If a single digit is already greater than k, the problem has no valid solution.
What is the best approach for Partition String Into Substrings With Values at Most K?
The greedy approach is the most efficient solution. Iterate through the string while forming the current numeric value and start a new substring whenever the value exceeds k. This guarantees the minimum number of partitions and runs in O(n) time with O(1) space.
Is Partition String Into Substrings With Values at Most K asked at Google/Amazon/Meta?
Problems combining greedy decisions with numeric string parsing commonly appear in interviews at companies like Amazon, Google, and Meta. Variations may involve minimizing partitions, validating substring ranges, or working with numeric constraints in strings.
What data structure is used in Partition String Into Substrings With Values at Most K?
The greedy solution does not require complex data structures. It uses simple integer accumulation while scanning a string. The alternative dynamic programming approach uses an array dp[] to store the minimum partitions for each prefix.
What is the time complexity of Partition String Into Substrings With Values at Most K?
The optimal greedy solution runs in O(n) time where n is the length of the string, since each digit is processed once. Space complexity is O(1) because only a running numeric value and a counter are maintained.