LeetCode Longest Substring with At Least K Repeating Characters

· 840 words · 2 minute read
2017年6月
LeetCode-分治

395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

方法

实际上这道题目很好的说明了分治和动态规划的联系。

使用动态规划方法的条件：

  • 最优子结构，即一个问题的最优解包含其子问题的最优解
  • 重叠子问题，即子问题与子问题之间不是相互独立的，是有联系的，前一个子问题的解为后一个子问题的解提供信息
  • 无后向性，具体的说，如果一个问题被划分为各个阶段后，阶段L中的状态只能由阶段L-1的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系
  • 一般性的，发现后面的值跟前面的有关系，要想到动态规划

使用分治算法的条件：

  • 一个规模为N的问题可以划分为k个规模较小的子问题，这些子问题互相独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。

回过头来看这道题目，一开始直接的认为这道题应该用动态规划的思想做，现在回头看一下动态规划的条件：子问题之间不相互独立。这道题的子问题相互独立吗？乍一看好像是不独立的，即求longestSubstring(s,k)需要求longestSubstring(s-1,k),求longestSubstring(s-1,k)需要求longestSubstring(s-2,k)，但是本人算法水平有限，想了好久也没有想出它的状态转换方程

那换个角度看看，即求至少存在K个重复字符的最长子串，那么对于小于K个的重复字符，实际上它起到了分隔的作用，从而把原字符串分隔成了几段，要找的满足重复的最长的子串一定在这几段中，对于分开的每段，又是同样性质的子问题，即子问题之间独立，故可以使用分治的方法进行求解。如果没有小于k的间隔，则直接返回这一段的长度，更新最大长度。

public class Solution {
    public int longestSubstring(String s, int k) {
        char[] c = s.toCharArray();
        return find(c,0,s.length(),k);
    }
    public int find(char[] c, int start, int end, int k){
        if(end-start < k){
            return 0;
        }
        int[] num = new int[26];
        for(int i = start; i < end; i++){
            int index = c[i] - 'a';
            num[index]++;
        }
        for(int i = start; i < end; i++){
            if(num[c[i]-'a'] < k && num[c[i]-'a'] > 0){
                int left = find(c,start,i,k);
                int right = find(c,i+1,end,k);
                return Math.max(left,right);
            }
        }
        return end - start;
    }
}
Share