Partition string into substrings with values at most k

String Dynamic Programming Greedy

47.5% acceptance

Feb 25, 2026

393

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. A substring is a contiguous sequence of characters within a string.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_partition(s: String, k: i32) -> i32 {
    let k = k as i64;
    let mut count = 1i32;
    let mut cur = 0i64;
    for b in s.bytes() {
      let d = (b - b'0') as i64;
      if d > k {
        return -1;
      }
      let next = cur * 10 + d;
      if next > k {
        count += 1;
        cur = d;
      } else {
        cur = next;
      }
    }
    count
  }
}