Readme

2522.Partition-String-Into-Substrings-With-Values-at-Most-K

这是一个很常规的dp题。我们令dp[i]表示前i个元素能够分成的最少分组。着眼点就是寻找最后一个区间的范围[j:i]。如果s[j:i]是小于等于k的，那么就有dp[i] = dp[j-1]+1。

那么我们是否需要遍历j找到最小的dp[j-1]呢？这样就是一个n^2的算法。事实上因为dp[i]必然是单调递增的，所以我们只需要找尽可能小的j，即能找到尽可能小的dp[j-1]。考虑k的长度是m，那么我们只需要考察最后一个区间长度如果是m能否可行。不可行的话，取最后一个区间的长度是m-1即可。

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