# Partition String Into Substrings With Values at Most K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-string-into-substrings-with-values-at-most-k)
Canonical: https://scaleengineer.com/dsa/problems/partition-string-into-substrings-with-values-at-most-k
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
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
## Dynamic Programming
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]`.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int partitionString(String s, int k) {
        int n = s.length();
        int[] dp = new int[n + 1];
        // Use n + 1 as a value for infinity, since the max partitions can be n.
        Arrays.fill(dp, n + 1);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            long currentNum = 0;
            long powerOf10 = 1;
            // Iterate backwards from i-1 to form the last substring s[j...i-1]
            for (int j = i - 1; j >= 0; j--) {
                // Optimization: A valid substring won't be longer than k's digits + 1
                if (i - j > 11) {
                    break;
                }

                int digit = s.charAt(j) - '0';
                currentNum = digit * powerOf10 + currentNum;

                if (currentNum > k) {
                    break; // Further extensions will also be > k
                }

                if (dp[j] < n + 1) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
                
                // Avoid overflow for powerOf10
                if (powerOf10 > k) { 
                    break;
                }
                powerOf10 *= 10;
            }
        }

        return dp[n] > n ? -1 : dp[n];
    }
}
```
### Algorithm
1. Create a DP array, `dp`, of size `n+1`, where `n` is the length of `s`.
2. Initialize `dp[0] = 0` and all other `dp[i]` to a value representing infinity (e.g., `n+1`).
3. Iterate from `i = 1` to `n` to compute `dp[i]`.
4. For each `i`, iterate backwards from `j = i-1` to `0` to form the last substring `s[j...i-1]`.
5. Build the numerical value of the substring `s[j...i-1]` iteratively.
6. 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`.
7. 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)`.
8. 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.

## 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.
**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.
**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).
### Explanation
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.

```java
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;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumPartition(string s, int k) {
    int n = s.size();
    int f[n];
    memset(f, 0, sizeof f);
    const int inf = 1 << 30;
    function<int(int)> dfs = [&](int i) -> int {
      if (i >= n)
        return 0;
      if (f[i])
        return f[i];
      int res = inf;
      long v = 0;
      for (int j = i; j < n; ++j) {
        v = v * 10 + (s[j] - '0');
        if (v > k)
          break;
        res = min(res, dfs(j + 1));
      }
      return f[i] = res + 1;
    };
    int ans = dfs(0);
    return ans < inf ? ans : -1;
  }
};

```

### Python

```python
class Solution:
    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

```