2522. Partition String Into Substrings With Values at Most K

Solution idea

1-D DP

Define DP[i] = the minimum number of substrings in a good partition of s[1...i] (prepend s with a placeholder)

Base Case: DP[0] = 0 because s[0] represents empty string

Recurrence (naive):

DP[i] = 1 + min(DP[j-1]) for $1 \leq j < i $ and $s[j:i] \leq k$

(注意：这种写法需要$O(n^2)$，题目给出的量级会超时。需要通过观察DP[i]的性质，优化Recurrence)

KEY: DP[i]的重要性质

• 注意到，DP[i]一定是 non-decreasing. i.e. 长度为100的字符串的good partition数量一定不可能比长度99时的该字符串的good partition数量少
• 利用这个性质，每次更新DP[i]时，就不用看过去所有的j，只用看两个地方的j:
  1. len(s[j:i]) == len(k): 首先看j使得s[j:i]位数与k的位数相同时的情况，如果此时框住的s[j:i]的值 $\leq k$, 说明DP[i]的最小是DP[j-1]+1。j不能再往前看了，因为框住的s[j:i]的位数比k的位数多，所以值一定比k大，不满足题意。
  2. 如果Case 1中框住的s[j:i]的值 $ > k$，说明相同位数时不能满足题意，那么，我们就需要缩短一位数s[j+1:i]，这样s[j+1:i]的值 一定$\leq k$ (e.g. 两位数一定小于三位数)，DP[i]的最小是DP[j]+1。j不用再往后看了，因为根据 DP[i]的重要性质，j再往后看，DP[j]也只会增加不会减少，所以肯定不存在最优

注意一下无解的情况。如果 k 长度是1，且s[i]里有一个字符大于k，那么说明即使区间长度是1 (最差情况下) 也无法满足要求。

Time complexity = $O(n)$

Space complexity = $O(n)$

Resource

【每日一题】LeetCode 2522. Partition String Into Substrings With Values at Most K