What is the main pattern used in Partition String Into Substrings With Values at Most K?

The problem primarily uses state transition dynamic programming combined with greedy substring extension to minimize the number of partitions.

How do I handle substrings that exceed the value k?

Whenever a substring value exceeds k, commit the previous substring and start a new substring; if a single digit exceeds k, return -1.

Can leading zeros affect the solution?

Since s contains digits 1-9 only, leading zeros do not appear, so the solution does not need to handle them.

What is the optimal way to compute substring values?

Compute values incrementally by multiplying the previous value by 10 and adding the new digit to avoid repeated parsing.

What are common mistakes when applying DP for this problem?

Common mistakes include over-parsing substrings, miscounting partitions, and neglecting the -1 return for impossible cases.

#2522

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

将字符串分割成值不超过 K 的子字符串

给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。如果一个字符串 s 的分割满足以下条件，我们称它是一个好分割： s 中每个数位恰好属于一个子字符串。每个子字符串的值都小于等于 k 。请你返回 s 所有的好分割中，子字符串的最少数目。如果不…

字符串动态规划贪心

题目描述

给你一个字符串 s ，它每一位都是 1 到 9 之间的数字组成，同时给你一个整数 k 。

如果一个字符串 s 的分割满足以下条件，我们称它是一个好分割：

s 中每个数位恰好属于一个子字符串。
每个子字符串的值都小于等于 k 。

请你返回 s 所有的好分割中，子字符串的最少数目。如果不存在 s 的好分割，返回 -1 。

注意：

一个字符串的值是这个字符串对应的整数。比方说，"123" 的值为 123 ，"1" 的值是 1 。
子字符串 是字符串中一段连续的字符序列。

示例 1：

输入：s = "165462", k = 60
输出：4
解释：我们将字符串分割成子字符串 "16" ，"54" ，"6" 和 "2" 。每个子字符串的值都小于等于 k = 60 。
不存在小于 4 个子字符串的好分割。

示例 2：

输入：s = "238182", k = 5
输出：-1
解释：这个字符串不存在好分割。

提示：

1 <= s.length <= 10⁵
s[i] 是 '1' 到 '9' 之间的数字。
1 <= k <= 10⁹

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i)$ 表示从字符串 $s$ 的下标 $i$ 开始的最少分割数，那么答案就是 $dfs(0)$ 。

函数 $dfs(i)$ 的计算过程如下：

如果 $i \geq n$ ，说明已经到达字符串末尾，返回 $0$ 。
否则，我们枚举 $i$ 开始的所有子字符串，如果子字符串的值小于等于 $k$ ，那么我们可以将子字符串作为一个分割，那么我们可以得到 $dfs(j + 1)$ ，其中 $j$ 是子字符串的末尾下标，然后我们取所有可能的分割中的最小值，再加上 $1$ ，即为 $dfs(i)$ 的值。

最后，如果 $dfs(0) = \infty$ ，说明不存在好分割，返回 $-1$ ，否则返回 $dfs(0)$ 。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串 $s$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

speed

复杂度分析

指标	值
时间	complexity is O(n) in greedy-enhanced DP, where n is the length of the string, because each character is processed once with constant work per substring check. Space complexity is O(n) for the DP array or O(1) if using only previous state tracking.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The interviewer may hint at using a DP array to track minimal partitions.
question_mark
Watch for questions on how to efficiently check substring numeric values against k.
question_mark
Expect prompts to optimize naive DP using greedy substring extensions.

warning

常见陷阱

外企场景

error
Attempting to parse entire substrings repeatedly without incremental computation, causing timeouts.
error
Starting new substrings too early or too late, which can overcount partitions.
error
Ignoring the case when a single digit exceeds k, leading to incorrect -1 return.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Partition string into substrings where each numeric value is at least L and at most K.
arrow_right_alt
Find the maximum number of valid substrings instead of minimum.
arrow_right_alt
Allow substrings to include leading zeros and adjust the value check accordingly.

help

常见问题

外企场景

继续练习

#2472 不重叠回文子字符串的最大数目 #2573 找出对应 LCP 矩阵的字符串 #2645 构造有效字符串的最少插入数