leetcode上的子串总结

leetcode刷了200多题了，但是感觉效果还不是特别好，做过的容易忘，所以打算以后总结一下题目经验~

这次专题就是字符串的子串问题，我发现很多都跟动态规划相关，然而动态规划是我的弱点啊，话不多说，先看看题

1.leetcode395

题意：

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求T中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:

输入:

s = "aaabb", k = 3

输出:

3

最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2:

输入:

s = "ababbc", k = 2

输出:

5

最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了3次

这题目我一看还以为又是动态规划，因为以前遇到过，但是吧，想不出递推关系啊，动态规划难点就在这里，咋整，多练吧，嘿嘿，然而这题其实是分治方法，我看的题解，确实想不到。先是遍历统计个数，然后小于要求个数的字符就以这个点分治，毕竟这个点不满足，肯定要把它排除在外嘛，然后在左右找最大值

---

public int longestSubstring(String s, int k) {

        return longS(s,k,0,s.length()-1);

    }

    private int longS(String s,int k,int start,int end){

        if(start>end)

            return 0;

        int co[]=new int[26];

        for(int i=start;i<=end;i++)

            co[s.charAt(i)-'a']++;

        for(int i=0;i<26;i++){

            if(co[i]<k&&co[i]>0){

                int position=s.indexOf((char)(i+'a'),start);

                return Math.max(longS(s,k,position+1,end),longS(s,k,start,position-1));

            }

        }

      return end-start+1; 

    }

---