Partition String Into Substrings With Values at Most K Solution
Partition String Into Substrings With Values at Most K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Partition String Into Substrings With Values at Most K is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google and Myntra interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Greedy
- Asked at: Amazon, Google, Myntra
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A partition of the digit string s is good when every part, read as a number, is at most k.
Return the minimum number of parts in a good partition, or -1 if none exists.
Example 1
Input: s = "165462", k = 60
Output: 4
Explanation: The parts "16", "54", "6" and "2" are each at most 60.
Example 2
Input: s = "238182", k = 5
Output: -1
Explanation: The digit 8 alone exceeds 5.
Example 3
Input: s = "3", k = 3
Output: 1
Constraints
1 <= s.length <= 100000s consists of digits.1 <= k <= 1000000000
Hints for Partition String Into Substrings With Values at Most K
Hint 1
If any single digit exceeds
k, no partition can work.Hint 2
Otherwise extend the current part as long as appending the next digit keeps it at or below
k.Hint 3
Test the overflow with a division rather than by building the number:
cur > (k - d) / 10.
How to solve Partition String Into Substrings With Values at Most K
A left-to-right greedy that makes each part as long as possible. Since making a part longer never forces more parts later, the greedy is optimal.
Approach
- Reject immediately if a digit exceeds
k. - Keep
cur, the value of the part being built; on each digit, check whethercur · 10 + dwould exceedk. - If it would, close the part, start a new one at this digit, and count it.
Why it works
Exchange argument: suppose an optimal partition ends a part earlier than the greedy would. Extending that part by one digit keeps it valid (the greedy said so) and only removes a digit from the next part, which stays valid because its value only shrinks. Repeating turns any optimal partition into the greedy one without increasing the count. The division form of the overflow test avoids building cur · 10 + d, which would exceed 32-bit range for large k.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
cur * 10 + doverflows a 32-bitintwhenkis near10^9— compare with(k - d) / 10instead, or widen the type.- The impossibility check must look at single digits, not at the whole string.
- The part count starts at 1, since even an empty scan produces one part.
Reference solution
Python
def minimumPartition(s: str, k: int) -> int:
count, cur = 1, 0
for ch in s:
d = int(ch)
if d > k:
return -1
if cur > (k - d) // 10:
count += 1
cur = d
else:
cur = cur * 10 + d
return countJava
public static int minimumPartition(String s, int k) {
int count = 1, cur = 0;
for (int i = 0; i < s.length(); i++) {
int d = s.charAt(i) - '0';
if (d > k) return -1;
if (cur > (k - d) / 10) {
count++;
cur = d;
} else {
cur = cur * 10 + d;
}
}
return count;
}C++
int minimumPartition(string s, int k) {
int count = 1, cur = 0;
for (char ch : s) {
int d = ch - '0';
if (d > k) return -1;
if (cur > (k - d) / 10) {
count++;
cur = d;
} else {
cur = cur * 10 + d;
}
}
return count;
}JavaScript
var minimumPartition = function(s, k) {
var count = 1, cur = 0;
for (var i = 0; i < s.length; i++) {
var d = s.charCodeAt(i) - 48;
if (d > k) return -1;
if (cur > Math.floor((k - d) / 10)) { count++; cur = d; }
else cur = cur * 10 + d;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming