Longest Substring Without Repeating Characters

犯错，只改变了左边窗口起始位置， 没有去删除左指针之前的元素。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int count = 0; int right = 0;int i=0;
        for(;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))) 
                map.put(s.charAt(i), i);
            else{
                System.out.println(i + " " + right + " " + (i-right));
                count = Math.max(count, i-right);
                right = map.get(s.charAt(i))+1;
                map.put(s.charAt(i), i);
            }
        }
        System.out.println(i + " " + right + " " + (i-right));
        count = Math.max(count, i-right);
        return count;
    }
}

正确解法

注意循环出来后需要判断。right pointer应该改名为left更恰当

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int count = 0; int right = 0;int i=0;
        for(;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))) 
                map.put(s.charAt(i), i);
            else{
                System.out.println(i + " " + right + " " + (i-right));
                count = Math.max(count, i-right);
                for(int j=right;j<s.length();j++){
                     map.remove(s.charAt(j));
                     if(s.charAt(j)==s.charAt(i)){
                         right = j+1; break;
                     }
                } 
                map.put(s.charAt(i), i);
            }
        }
        System.out.println(i + " " + right + " " + (i-right));
        count = Math.max(count, i-right);
        return count;
    }
}

Longest Substring with At Most K Distinct Characters (G)

这道题需要注意的是最后corner case的判断。G的follow up是如果输入的不是有限长度字符串，而是char stream，这时需要一个额外的map来保存每个字符最后出现的位置。

当map size>k时，left指针移动到下一个最近的“字符最后位置”，删除这个char, map size-1。

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int left = 0;
        int result = 0;
        for(int i=0;i<s.length();i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                map.put(ch, map.get(ch)+1);
            }
            else
                map.put(ch,1);

            if(map.size()>k){
                result = Math.max(result, i-left); //key point: since we get as longest as possible, so we process here. not inside loop
                while(map.size()>k){
                    char cr = s.charAt(left);
                    if(map.get(cr)==1){
                        map.remove(cr);
                    }
                    else
                        map.put(cr,map.get(cr)-1);
                    left++;       
                }
            }
        }

        // in case, k=2, acaaaaaaaaaaaaaa, left = 1, answer is caaaaaaaaaaaaaa, map.size()==2
        result = Math.max(result, s.length()-left);
        return result;
    }
}

Count The Repetitions

related tag是DP，也是无语。暴力解法two pointers也能过。

public class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int count1 = 0; int count2 = 0; char[] arr1 = s1.toCharArray(); char[] arr2 = s2.toCharArray();
        int i=0;int j=0;
        while(count1<n1){
            if(arr1[i]==arr2[j]){
                j++;
            }
            i++;
            if(j==arr2.length){
                j=0; count2++;
            }
            if(i==arr1.length){
                i=0;count1++;
            }
        }
        return count2/n2;
    }
}

高端解法是求string的余数，会形成loop。以后再研究。

The key is, we just need to calculate what will remain after s1 obtains s2.

That is, (s1, s2) -> (sRemain, matchCnt); for example,
(abcd, ab) -> (cd, 1)
(ababa, ab) -> (a, 2)
(a, aaaa) -> (a, 0)
(aabaabaab, aba) -> (ab, 2) as aabaaba exactly matches aba twice.

And, each time we append s1 to the remain string, to make a sequence: (Using [] to mark the remain string)
(abcd, ab): abcd -> [cd]abcd -> [cd]abcd -> [cd]abcd -> ...
(ababa, ab): ababa -> [a]ababa -> [a]ababa -> [a]ababa -> ...
(a, aaaa): a -> [a]a -> [aa]a -> [aaa]a -> a -> [a]a -> [aa]a -> ...
(aabaabaab, aba): aabaabaab -> [ab]aabaabaab -> [ab]aabaabaab -> ...

Obviously, there will be a loop in the sequence, assume the length of loop is loop, and the length before the loop is k.
(abcd, ab): loop=1, k=1
(a, aaaa): loop=4, k=0
(aabaabaab, aba): loop=1, k=1