leetcode3:longest-substring-without-repeating-characters

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
           

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
           

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is"wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
           

二 分析

  给定一个字符串，找到不同字符的最长子字符串。这是一道典型的滑动窗口的问题。

直观的双重for去遍历效率不高（N方）。滑动窗口常用来解决求字符串子串问题，借助hashmap和计数器，其能在O(n)时间复杂度求子串问题。涉及这块的代码有套路的。题目做的少我还没总结，看大神有些专题整理类似的问题。

     通常检查子串里面是否有重复字母，可以用遍历一遍方法，这样会慢，更快的是hashset,O(1)

假设有数组[a b c d e f g h]
一个大小为3的滑动窗口在其上滑动，则有:
[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]
           

 下面我试着翻译下官网的滑动窗口的解释：

    滑动窗口是个抽象概念通常用来解决数组或者字符串的问题，它有通过start\end定义起止的一系列数组、字符串元素组成。

沿用数学的开闭区间的概念如[i,j）。如果我们把滑动窗口的两个边界沿一定方向，向右滑动1，就可以表示为：[i,j)-->[i+1,j+1)

      回到我们的题目本身，我们用hashset保存当前窗口[i,j,初始化是i=j）的字符。然后我们把窗口右边界j向右滑动，如果j对应的字母在hashset不存在,则继续向右滑动j.直到s[j]已经在hashset存在，这时候我们计算从i开始无重复字母的最大子串的长度（窗口的长度）。如果我们对于所有的i执行上面的操作，就能获取到最终的结果。

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int res = lengthOfLongestSubstring("aab");
		System.out.println(res);
		 res = lengthOfLongestSubstring("pwwkew");
		System.out.println(res);
		 res = lengthOfLongestSubstring("aabaab!bb");
			System.out.println(res);
	}

	
	public static int lengthOfLongestSubstring(String s) {
         if(s == null || s.length()==0){
        	return 0;
        }
		int begin=0;
		int end =0;
		int res =0;
		 Set<Character> set = new HashSet<>();
		
		while(end< s.length()&&begin< s.length()){
			if(!set.contains(s.charAt(end))){
				set.add(s.charAt(end));		
				
				res = Math.max(res, end-begin+1);
				end++;//R向右滑动
			}
			else{//repeat
				set.remove(s.charAt(begin++));//L向右滑动
				
		    }			
		}	
		return res;
    }
           

Runtime: 3 ms, faster than 91.66% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 36 MB, less than 100.00% of Java online submissions forLongest Substring Without Repeating Characters.

最开始，我想用26字母的数组，但是提交后不通过，有类似的aabaab!bb 。特殊字符-‘a’就提示越界异常了。

关键点如下：

        sliding window 定长/不定长？

        sliding window (L/R) 起点？

        hash_table 中存的什么数据以及它们的物理意义？

        什么时候移动 L pointer?

        什么时候移动 R pointer?

        根据题意counter（状态条件）是什么？