Scale Engineer

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 ProgrammingGreedy
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 <= 105
  • s[i] is a digit from '1' to '9'.
  • 1 <= k <= 109

 

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

  1. Initialize partitions = 1 and currentValue = 0L.
  2. Iterate through the string s from left to right, character by character.
  3. For each character c, get its integer value digit.
  4. First, check if digit > k. If it is, a single-digit substring is already too large, so no solution exists. Return -1.
  5. Try to append the digit to the current number being formed: newValue = currentValue * 10 + digit.
  6. If newValue is less than or equal to k, update currentValue = newValue and continue to the next character.
  7. 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.
  8. 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.

class Solution {    public int partitionString(String s, int k) {        int partitions = 1;        long currentValue = 0;         for (int i = 0; i < s.length(); i++) {            int digit = s.charAt(i) - '0';             // Edge case: a single digit is larger than k.            if (digit > k) {                return -1;            }             // Check if adding the current digit would exceed k.            if (currentValue * 10 + digit <= k) {                currentValue = currentValue * 10 + digit;            } else {                // End the current partition and start a new one.                partitions++;                currentValue = digit;            }        }                return partitions;    }}

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

Solutions

class Solution {private  Integer[] f;private  int n;private  String s;private  int k;private  int inf = 1 << 30;public  int minimumPartition(String s, int k) {    n = s.length();    f = new Integer[n];    this.s = s;    this.k = k;    int ans = dfs(0);    return ans < inf ? ans : -1;  }private  int dfs(int i) {    if (i >= n) {      return 0;    }    if (f[i] != null) {      return f[i];    }    int res = inf;    long v = 0;    for (int j = i; j < n; ++j) {      v = v * 10 + (s.charAt(j) - '0');      if (v > k) {        break;      }      res = Math.min(res, dfs(j + 1));    }    return f[i] = res + 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 →

Next problem