Partition String Into Substrings With Values at Most K

Partition String Into Substrings With Values at Most K

What is this problem about?

The Partition String Into Substrings With Values at Most K problem asks you to partition a numeric string into the minimum number of substrings where each substring's integer value is ≤ k. This coding problem uses greedy: extend the current substring as long as its value stays ≤ k. When a single digit exceeds k, return -1. The string, greedy, and dynamic programming interview pattern is demonstrated.

Why is this asked in interviews?

Google asks this to test greedy string partitioning with a numeric value constraint. The greedy approach — always extend the current partition as far as possible without exceeding k — minimizes the number of partitions.

Algorithmic pattern used

Greedy extension. Scan characters: maintain current number by extending: curr = curr * 10 + digit. If curr > k, start a new partition (count++, reset curr = digit). If digit > k at any point (even as a single number), return -1. Return final count (initialized to 1 if string is non-empty).

Example explanation

s="165462", k=60.

• Scan: 1→1, 16→16, 16*10+5=165>60 → new partition! count=2, curr=5.
• 54→54, 54*10+6=546>60 → count=3, curr=6.
• 62→62>60 → count=4, curr=2. Result: 4 partitions: "16","5","46"... wait, recalculate. "1"(1),"6"(6)→"16">60? no wait k=60: 16≤60. Continue: 165>60 → new. curr=5. 54>60? No. 546>60 → new. curr=6. 62>60 → new. curr=2. Final string exhausted. Count=4. 4 partitions.

Common mistakes candidates make

• Not handling single digits > k (must return -1).
• Not resetting curr correctly when starting a new partition.
• Using '0' as a character instead of digit value.
• Not initializing count to 1.

Interview preparation tip

Numeric string partition problems using a value threshold always use greedy extension: build the current number digit by digit, reset when it exceeds the threshold. The impossible case (single digit > k) must be checked immediately. This same greedy approach applies to "minimum number of splits to make string value ≤ k" in various numerical contexts. Practice similar problems with different value functions.