Partition String Into Substrings With Values at Most K

MEDIUM

Description

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

Checkout 2 different approaches to solve Partition String Into Substrings With Values at Most K. Click on different approaches to view the approach and algorithm in detail.

Greedy Approach

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.

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 Analysis

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

Pros and Cons

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

Code Solutions

Checking out 3 solutions in different languages for Partition String Into Substrings With Values at Most K. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Partition String Into Substrings With Values at Most K

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

String