Partition String Into Substrings With Values at Most K

Med

#2302Time: O(N), where N is the length of the string `s`. We iterate through the string exactly once.Space: O(1). We only use a few variables to store the count and the current value, regardless of the input string size.

Patterns

Dynamic Programming Greedy

Data structures

String

Prompt

You are given a string s consisting of digits from 1 to 9 and an integer k.

A partition of a string s is called good if:

Each digit of s is part of exactly one substring.
The value of each substring is less than or equal to k.

Return the minimum number of substrings in a good partition of s. If no good partition of s exists, return -1.

Note that:

The value of a string is its result when interpreted as an integer. For example, the value of "123" is 123 and the value of "1" is 1.
A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "165462", k = 60
Output: 4
Explanation: We can partition the string into substrings "16", "54", "6", and "2". Each substring has a value less than or equal to k = 60.
It can be shown that we cannot partition the string into less than 4 substrings.

Example 2:

Input: s = "238182", k = 5
Output: -1
Explanation: There is no good partition for this string.

Constraints:

1 <= s.length <= 10⁵
s[i] is a digit from '1' to '9'.
1 <= k <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This problem exhibits a key property: a greedy choice leads to a globally optimal solution. The greedy strategy is to make each substring as long as possible without its value exceeding k. By maximizing the length of the current substring, we push the start of the next substring as far right as possible, which intuitively minimizes the total number of substrings needed.

Algorithm

Initialize partitions = 1 and currentValue = 0L.
Iterate through the string s from left to right, character by character.
For each character c, get its integer value digit.
First, check if digit > k. If it is, a single-digit substring is already too large, so no solution exists. Return -1.
Try to append the digit to the current number being formed: newValue = currentValue * 10 + digit.
If newValue is less than or equal to k, update currentValue = newValue and continue to the next character.
If newValue is greater than k, the current substring cannot be extended further. We must start a new partition. Increment partitions and reset currentValue to the current digit.
After iterating through the entire string, return the total partitions count.

Walkthrough

We can solve this problem with a single pass through the string. We maintain a count of partitions and the numerical value of the substring we are currently building.

We start with partitions = 1 and currentValue = 0. We iterate through the string's characters one by one. For each digit, we check if adding it to our currentValue would make it exceed k.

If currentValue * 10 + digit <= k, it's safe to extend the current substring. We update currentValue and move to the next digit.
If currentValue * 10 + digit > k, we cannot extend the current substring. We must end it here and start a new one. We increment our partitions count and reset currentValue to be the current digit, as it will be the first digit of the new substring.

An important edge case is when a single digit is larger than k. For example, if s = "...8..." and k = 5. In this case, no valid partition is possible because the substring "8" itself is invalid. We must handle this by returning -1.

This greedy approach is both simple and highly efficient.

1class Solution {2    public int partitionString(String s, int k) {3        int partitions = 1;4        long currentValue = 0;5 6        for (int i = 0; i < s.length(); i++) {7            int digit = s.charAt(i) - '0';8 9            // Edge case: a single digit is larger than k.10            if (digit > k) {11                return -1;12            }13 14            // Check if adding the current digit would exceed k.15            if (currentValue * 10 + digit <= k) {16                currentValue = currentValue * 10 + digit;17            } else {18                // End the current partition and start a new one.19                partitions++;20                currentValue = digit;21            }22        }23        24        return partitions;25    }26}

Complexity

Time

O(N), where N is the length of the string `s`. We iterate through the string exactly once.

Space

O(1). We only use a few variables to store the count and the current value, regardless of the input string size.

Trade-offs

Pros

Extremely efficient with O(N) time complexity.
Optimal space complexity of O(1).
Simple to understand and implement.

Cons

The greedy choice is not always optimal for every partitioning problem, so its applicability is limited. Proving its correctness for this specific problem requires a separate argument (an exchange argument).

A standard way to solve partitioning problems is using dynamic programming. This approach builds the solution for the entire string by solving it for all its prefixes. We define a state dp[i] as the minimum number of substrings required for a good partition of the prefix s[0...i-1].

Algorithm

Create a DP array, dp, of size n+1, where n is the length of s.
Initialize dp[0] = 0 and all other dp[i] to a value representing infinity (e.g., n+1).
Iterate from i = 1 to n to compute dp[i].
For each i, iterate backwards from j = i-1 to 0 to form the last substring s[j...i-1].
Build the numerical value of the substring s[j...i-1] iteratively.
The length of any valid substring cannot be much larger than the number of digits in k. We can break the inner loop if the substring becomes too long (e.g., more than 10 digits) or its value exceeds k.
If the value of s[j...i-1] is less than or equal to k and dp[j] is reachable (not infinity), update dp[i] with the minimum value: dp[i] = min(dp[i], dp[j] + 1).
After the loops complete, if dp[n] is still infinity, it means no solution exists, so return -1. Otherwise, dp[n] holds the minimum number of partitions.

Walkthrough

We use a DP array, dp, of size n+1, where dp[i] stores the minimum partitions for the prefix of length i. The base case is dp[0] = 0, as an empty string requires zero partitions. We initialize the rest of the dp array with a large value to represent infinity.

The core of the algorithm is the transition formula. To compute dp[i], we consider all possible last substrings that end at index i-1. Such a substring can start at any index j where 0 <= j < i. If the substring s[j...i-1] represents a value less than or equal to k, we can form a partition by taking the optimal solution for the prefix s[0...j-1] (which is dp[j]) and adding this one last substring. We want the minimum, so we take the minimum over all valid j's: dp[i] = min(dp[j] + 1).

A naive implementation would be O(N^2), but we can optimize it. Since k <= 10^9, any valid substring will have at most 10 digits. This means the inner loop that checks for the last substring only needs to look back about 10 characters, not all the way to the beginning. This optimization reduces the time complexity significantly, making it feasible for the given constraints.

1import java.util.Arrays;2 3class Solution {4    public int partitionString(String s, int k) {5        int n = s.length();6        int[] dp = new int[n + 1];7        // Use n + 1 as a value for infinity, since the max partitions can be n.8        Arrays.fill(dp, n + 1);9        dp[0] = 0;10 11        for (int i = 1; i <= n; i++) {12            long currentNum = 0;13            long powerOf10 = 1;14            // Iterate backwards from i-1 to form the last substring s[j...i-1]15            for (int j = i - 1; j >= 0; j--) {16                // Optimization: A valid substring won't be longer than k's digits + 117                if (i - j > 11) {18                    break;19                }20 21                int digit = s.charAt(j) - '0';22                currentNum = digit * powerOf10 + currentNum;23 24                if (currentNum > k) {25                    break; // Further extensions will also be > k26                }27 28                if (dp[j] < n + 1) {29                    dp[i] = Math.min(dp[i], dp[j] + 1);30                }31                32                // Avoid overflow for powerOf1033                if (powerOf10 > k) { 34                    break;35                }36                powerOf10 *= 10;37            }38        }39 40        return dp[n] > n ? -1 : dp[n];41    }42}

Complexity

Time

O(N * log K). The outer loop runs N times. The inner loop runs at most `d` times, where `d` is the number of digits in `k` (which is roughly `log10(K)`), due to the optimization that a valid substring cannot be much longer than `k`.

Space

O(N), where N is the length of the string `s`. This is required for the `dp` array.

Trade-offs

Pros

Guaranteed to find the optimal solution.
It is a systematic approach applicable to a wide range of sequence partitioning problems.

Cons

Higher space complexity of O(N) due to the DP array.
More complex to implement and reason about compared to the greedy solution.
Slightly slower than the optimal greedy approach.

Solutions

Solution

1class Solution {2private3  Integer[] f;4private5  int n;6private7  String s;8private9  int k;10private11  int inf = 1 << 30;12public13  int minimumPartition(String s, int k) {14    n = s.length();15    f = new Integer[n];16    this.s = s;17    this.k = k;18    int ans = dfs(0);19    return ans < inf ? ans : -1;20  }21private22  int dfs(int i) {23    if (i >= n) {24      return 0;25    }26    if (f[i] != null) {27      return f[i];28    }29    int res = inf;30    long v = 0;31    for (int j = i; j < n; ++j) {32      v = v * 10 + (s.charAt(j) - '0');33      if (v > k) {34        break;35      }36      res = Math.min(res, dfs(j + 1));37    }38    return f[i] = res + 1;39  }40}

1class Solution {2public:3  int minimumPartition(string s, int k) {4    int n = s.size();5    int f[n];6    memset(f, 0, sizeof f);7    const int inf = 1 << 30;8    function<int(int)> dfs = [&](int i) -> int {9      if (i >= n)10        return 0;11      if (f[i])12        return f[i];13      int res = inf;14      long v = 0;15      for (int j = i; j < n; ++j) {16        v = v * 10 + (s[j] - '0');17        if (v > k)18          break;19        res = min(res, dfs(j + 1));20      }21      return f[i] = res + 1;22    };23    int ans = dfs(0);24    return ans < inf ? ans : -1;25  }26};

1class Solution:2    def minimumPartition(self, s: str, k: int) -> int: @ cache def dfs(i): if i >= n: return 0 res, v = inf, 0 for j in range(i, n): v = v * 10 + int(s[j]) if v > k: break res = min(res, dfs(j + 1)) return res + 1 n = len(s) ans = dfs(0) return ans if ans < inf else - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem