Partition String Into Substrings With Values at Most K — Medium Problem & Solution

A partition of the digit string s is good when every part, read as a number, is at most k.

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 <= 100000
s consists of digits.
1 <= k <= 1000000000

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 whether cur · 10 + d would exceed k.
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 + d overflows a 32-bit int when k is near 10^9 — compare with (k - d) / 10 instead, 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue