LeetCode Problem 2522

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Greedy

Solution

LeetCode 2522 - Partition String Into Substrings With Values at Most K

Problem Understanding

The problem gives us a numeric string s, where every character is a digit between '1' and '9', and an integer k. We must split the string into contiguous substrings such that every substring, when interpreted as an integer, has a value less than or equal to k.

The goal is to minimize the number of substrings in the partition.

A partition must satisfy two important conditions:

1. Every character in the string must belong to exactly one substring.
2. Every resulting substring must represent a number less than or equal to k.

If no valid partition exists, we return -1.

For example, suppose:

s = "165462"
k = 60

One valid partition is:

"16" | "54" | "6" | "2"

All numbers are at most 60, and we used 4 substrings.

The constraints are very important:

• s.length can be as large as 10^5
• k can be as large as 10^9

These limits immediately tell us that expensive exponential or quadratic algorithms will not work. We need a highly efficient solution, ideally linear time.

Another key observation is that the digits are only from '1' to '9'. There are no leading zeros to worry about, which simplifies parsing and comparisons.

Several edge cases are important:

• A single digit may already be larger than k. In that case, no partition is possible.
• The optimal partition is not necessarily balanced. Sometimes we want very long substrings, sometimes short ones.
• Since the string can be very large, repeatedly converting large substrings into integers would be too slow if done naively.

Approaches

Brute Force Approach

A brute force solution would try every possible way to partition the string.

For a string of length n, there are 2^(n-1) possible partition patterns because every gap between characters can either contain a cut or not contain a cut.

For each partition configuration, we would:

1. Construct all substrings.
2. Convert each substring into an integer.
3. Verify every substring is at most k.
4. Track the minimum number of substrings among valid partitions.

This approach is correct because it exhaustively checks every possible partition, guaranteeing that the minimum valid partition count is found.

However, it is far too slow. With n = 10^5, exponential complexity is completely infeasible.

Key Insight

The important observation is that to minimize the number of substrings, we should make each substring as large as possible before cutting.

Suppose we are building the current substring from left to right. As long as appending the next digit keeps the numeric value less than or equal to k, extending the substring is always beneficial because:

• Longer substrings mean fewer total partitions.
• Cutting earlier can never reduce the total number of partitions.

This naturally leads to a greedy strategy.

We process the string from left to right:

• Keep extending the current number.
• If appending the next digit would exceed k, start a new substring.
• If even a single digit exceeds k, return -1.

This works because every greedy extension maximizes the current substring length, which minimizes the total number of substrings overall.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Tries every possible partition
Optimal Greedy	O(n)	O(1)	Extends each substring as much as possible

Algorithm Walkthrough

1. Initialize a counter partitions to 1 because we start with one substring.
2. Initialize current_value to 0. This variable represents the numeric value of the current substring being built.
3. Iterate through each character in the string.
4. Convert the current character into its digit value.
5. Before appending the digit, check whether the digit itself is greater than k.

If it is, then no valid partition exists because even a single-character substring would violate the condition. Return -1. 6. Compute the new value if we append the digit:

new_value = current_value * 10 + digit

7. If new_value <= k, extend the current substring by updating:

current_value = new_value

8. Otherwise, we must start a new substring because appending the digit would exceed k.

Increment the partition count:

partitions += 1

Start the new substring using the current digit alone:

current_value = digit

9. After processing all characters, return partitions.

Why it works

The greedy choice is always optimal because every partition boundary increases the answer by one. Therefore, we should delay partitioning as long as possible.

If extending the current substring still keeps its value at most k, creating a cut earlier would only increase the total number of substrings without providing any benefit. Thus, greedily taking the longest possible valid substring at every step produces the minimum number of partitions.

Python Solution

class Solution:
    def minimumPartition(self, s: str, k: int) -> int:
        partitions = 1
        current_value = 0

        for ch in s:
            digit = int(ch)

            if digit > k:
                return -1

            new_value = current_value * 10 + digit

            if new_value <= k:
                current_value = new_value
            else:
                partitions += 1
                current_value = digit

        return partitions

The implementation follows the greedy algorithm directly.

The variable partitions tracks how many substrings have been formed so far. We initialize it to 1 because the algorithm always begins with one active substring.

The variable current_value stores the numeric value of the substring currently being built.

For each character:

• We convert it into a digit.
• We immediately check whether the digit itself exceeds k.
• We attempt to append the digit to the current substring.
• If the resulting value remains valid, we continue extending.
• Otherwise, we create a new partition and restart from the current digit.

The algorithm processes each character exactly once, making it highly efficient for large inputs.

Go Solution

func minimumPartition(s string, k int) int {
    partitions := 1
    currentValue := 0

    for _, ch := range s {
        digit := int(ch - '0')

        if digit > k {
            return -1
        }

        newValue := currentValue*10 + digit

        if newValue <= k {
            currentValue = newValue
        } else {
            partitions++
            currentValue = digit
        }
    }

    return partitions
}

The Go implementation is almost identical to the Python version.

A few Go-specific details are worth noting:

• Characters are iterated as runes, so we convert using ch - '0'.
• Integer arithmetic is safe because k <= 10^9, which fits comfortably inside Go's int.
• No additional slices or arrays are required, so the space usage remains constant.

Worked Examples

Example 1

s = "165462"
k = 60

We process the string from left to right.

Step	Digit	Current Value Before	New Value	Action	Partitions
1	1	0	1	Extend	1
2	6	1	16	Extend	1
3	5	16	165	Too large, split	2
4	4	5	54	Extend	2
5	6	54	546	Too large, split	3
6	2	6	62	Too large, split	4

Final partition:

"16" | "54" | "6" | "2"

Answer:

4

Example 2

s = "238182"
k = 5

Step	Digit	Check
1	2	Valid
2	3	Valid
3	8	8 > 5

Since a single digit exceeds k, no valid partition exists.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once
Space	O(1)	Only a few integer variables are used

The algorithm scans the string exactly one time. Every iteration performs constant-time arithmetic and comparisons, so the total runtime is linear in the string length.

No auxiliary data structures proportional to input size are allocated, which keeps the space complexity constant.

Test Cases

sol = Solution()

assert sol.minimumPartition("165462", 60) == 4  # provided example
assert sol.minimumPartition("238182", 5) == -1  # impossible partition

assert sol.minimumPartition("1", 1) == 1  # single digit equal to k
assert sol.minimumPartition("9", 8) == -1  # single digit greater than k

assert sol.minimumPartition("1234", 1000) == 2  # "123" | "4"
assert sol.minimumPartition("1234", 9999) == 1  # entire string valid

assert sol.minimumPartition("999999", 9) == 6  # every digit must stand alone
assert sol.minimumPartition("11111", 11) == 3  # "11" | "11" | "1"

assert sol.minimumPartition("1000", 1000) == 1  # exact boundary match
assert sol.minimumPartition("1000", 100) == -1  # digit valid but grouping impossible

assert sol.minimumPartition("31415926", 1000) == 3  # mixed partition sizes

assert sol.minimumPartition("222222", 22) == 3  # repeated two-digit grouping
assert sol.minimumPartition("222222", 222222) == 1  # entire string valid

assert sol.minimumPartition("987654321", 100) == 5  # frequent splits

assert sol.minimumPartition("7777777", 777) == 3  # repeated maximal grouping

Test Summary

Test	Why
"165462", 60	Validates the provided example
"238182", 5	Validates impossible case
"1", 1	Smallest valid input
"9", 8	Single digit exceeding k
"1234", 1000	Requires one split
"1234", 9999	Entire string fits
"999999", 9	Every digit isolated
"11111", 11	Greedy pairing behavior
"1000", 1000	Exact upper boundary
"1000", 100	Partition impossible despite valid digits
"31415926", 1000	Mixed substring lengths
"222222", 22	Repeated equal groups
"222222", 222222	Single partition
"987654321", 100	Frequent overflow checks
"7777777", 777	Repeated maximal valid chunks

Edge Cases

One important edge case occurs when a single digit is already larger than k. For example:

s = "9"
k = 5

No valid partition exists because every substring must contain at least one digit, and the single digit already violates the constraint. The implementation handles this immediately with the check:

if digit > k:
    return -1

Another important case happens when the entire string is already less than or equal to k. For example:

s = "123"
k = 1000

In this situation, the optimal answer is 1 because no splits are needed. The greedy algorithm naturally achieves this because it only creates a new partition when appending another digit would exceed k.

A more subtle edge case appears when repeated extensions frequently exceed k. Consider:

s = "999999"
k = 9

Every attempt to append another digit immediately exceeds the limit, forcing every digit into its own substring. The algorithm correctly handles this by creating a new partition whenever the extended value becomes too large.

Another tricky scenario involves exact boundary matches. For example:

s = "1000"
k = 1000

The substring value is exactly equal to k, which is allowed. Since the condition uses <= k, the implementation correctly keeps extending the substring instead of splitting unnecessarily.