Leetcode003 Longest Substring Without Repeating Characters

Problem:

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.

Intuition:

这个题目总体来说就是运用了滑动窗口的思想。如果算法题中一旦出现了固定长度求最值或者提供限制条件求最大长度的时候就应该有使用这个算法的意识。

如果是固定长度求最值的问题（譬如求数组中连续k个元素最大的和），那么我们就先指定两个下标i，j(j=i+k-1)，对k个元素长的子数组进行求和，然后每次移动i的时候，j也往相同方向移动一格，这样就可以在O(n)的时间复杂度内得到答案。

如果是限制条件求最大长度的问题（譬如本题），只需在每次移动下标的时候用set对新元素进行检查，如果成功就把j往后移，继续扩展数组长度。否则将i往后移看是否能规避冲突。

给一个滑动窗口算法相关的讨论链接：https://www.zhihu.com/question/314669016

以后如果有时间会在博客中讨论这个话题。

Solution:

public static int lengthOfLongestSubstringSolution(String s){
      //被答案吊打了。这一题答案采用的是滑动窗口的思想。i表示滑动窗口的头，j表示滑动窗口的尾
      //自己之前没有想到这种方法是因为默认就觉得要用for循环遍历字符串，游标必然++，那么一旦冲突不一定是和第一个字符冲突
      //用滑动窗口就发现在答案算法中就算不和第一个字符冲突，它i往后移动迟早会碰到冲突部分。
      //这题要理解这种算法直接在头脑中想象一个滑动窗口和一个特殊字符串pwwkew就容易了
      int n=s.length();
      Set<Character> set=new HashSet<>();
      int ans=0,i=0,j=0;
      while(i<n&&j<n){
          if(!set.contains(s.charAt(j)))  {
              set.add(s.charAt(j++));
              ans=Math.max(ans,j-i);
          }else{
              set.remove(s.charAt(i++));
          }
      }
      return ans;

  }