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.

Examples

Example 1

1
2
3
4

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

1
2
3

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

Constraints

  • 1 <= s.length <= 10^5
  • s[i] is a digit from '1' to '9'.
  • 1 <= k <= 10^9

Solution

Method 1 - Greedy Partition

Intuition

We want to minimize the number of substrings such that each substring’s integer value is at most k. The greedy approach is to make each substring as long as possible without exceeding k.

Approach

  1. Start from the first character and try to extend the current substring by adding digits until the value would exceed k.
  2. When the value would exceed k, start a new substring from the current digit.
  3. If any single digit is greater than k, return -1.
  4. Count the number of substrings formed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <string>
using namespace std;
int minimumPartition(string s, int k) {
    int n = s.size(), ans = 1;
    long long cur = 0;
    for (char c : s) {
        int d = c - '0';
        if (d > k) return -1;
        if (cur * 10 + d > k) {
            ++ans;
            cur = d;
        } else {
            cur = cur * 10 + d;
        }
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func minimumPartition(s string, k int) int {
    ans := 1
    cur := 0
    for _, c := range s {
        d := int(c - '0')
        if d > k { return -1 }
        if cur*10+d > k {
            ans++
            cur = d
        } else {
            cur = cur*10 + d
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int minimumPartition(String s, int k) {
        int ans = 1;
        long cur = 0;
        for (char c : s.toCharArray()) {
            int d = c - '0';
            if (d > k) return -1;
            if (cur * 10 + d > k) {
                ans++;
                cur = d;
            } else {
                cur = cur * 10 + d;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

fun minimumPartition(s: String, k: Int): Int {
    var ans = 1
    var cur = 0L
    for (c in s) {
        val d = c - '0'
        if (d > k) return -1
        if (cur * 10 + d > k) {
            ans++
            cur = d.toLong()
        } else {
            cur = cur * 10 + d
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def minimumPartition(s: str, k: int) -> int:
    ans = 1
    cur = 0
    for c in s:
        d = int(c)
        if d > k:
            return -1
        if cur * 10 + d > k:
            ans += 1
            cur = d
        else:
            cur = cur * 10 + d
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

pub fn minimum_partition(s: String, k: i64) -> i32 {
    let mut ans = 1;
    let mut cur = 0i64;
    for c in s.chars() {
        let d = c.to_digit(10).unwrap() as i64;
        if d > k { return -1; }
        if cur * 10 + d > k {
            ans += 1;
            cur = d;
        } else {
            cur = cur * 10 + d;
        }
    }
    ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function minimumPartition(s: string, k: number): number {
    let ans = 1;
    let cur = 0;
    for (const c of s) {
        const d = Number(c);
        if (d > k) return -1;
        if (cur * 10 + d > k) {
            ans++;
            cur = d;
        } else {
            cur = cur * 10 + d;
        }
    }
    return ans;
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of s.
  • 🧺 Space complexity: O(1) (constant extra space).