How to solve substring problems?

3.Longest Substring Without Repeating Characters

1-split window

Or Using HashMap To store the latest index of the character.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0)
            return 0;
        int[] map = new int[256];
        int left = 0, right = 0;
        int ans = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            if(map[c] == 0){
                map[c] = 1;
                ans = Math.max(ans, right - left + 1);
                right++;
            }
            else{
                while(s.charAt(left) != c){
                    map[s.charAt(left)] = 0;
                    left++;
                }
                map[c] = 0;
                left++;
            }
        }
        return ans;

    }
}

395.Longest Substring with At Least K Repeating Characters

目前处理子串的方法有：

（1）双指针；

（2）dp；

（3）分治；

http://blog.csdn.net/u010900754/article/details/62159601

1-Split

class Solution {
    public int longestSubstring(String s, int k) {
        if(s == null || s.length() < k)
            return 0;
        if(k == 1)
            return s.length();
        int[] cnt = new int[26];
        for(int i = 0; i < s.length(); i++){
            cnt[s.charAt(i) - 'a']++;
        }
        int badCharIndex = -1;
        for(int i = 0; i < cnt.length; i++){
            if(cnt[i] > 0 && cnt[i] < k){
                badCharIndex = i;
                break;
            }
        }
        if(badCharIndex == -1)
            return s.length();

        char badChar = (char) (badCharIndex + 'a');
        String[] parts = s.split(badChar + "");
        int ans = 0;
        for(String part : parts){
            ans = Math.max(ans, longestSubstring(part, k));
        }
        return ans;
    }
}