Partition String Into Substrings With Values at Most K

Medium
862.

Partition String Into Substrings With Values at Most K

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var minimumPartition = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Partition String Into Substrings With Values at Most K

  1. Hint 1

    If any single digit exceeds k, no partition can work.

  2. Hint 2

    Otherwise extend the current part as long as appending the next digit keeps it at or below k.

  3. 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

  1. Reject immediately if a digit exceeds k.
  2. Keep cur, the value of the part being built; on each digit, check whether cur · 10 + d would exceed k.
  3. 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

Java

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