LeetCode 3. Longest Substring Without Repeating Characters

原题链接在这里：https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目：

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

题解：

快慢指针维护substring的方法在Minimum Window Substring里有总结.

窗口[walker,runner]. walker, runner都是向右移，维护map, 用来存储扫过char的frequency. 首先右侧窗口runner在前跑，扫过char的frequency 加一. 直到遇到frequency已经大于零, 说明前面有相同元素, runner停下移动walker. walker 扫过char的frequency减一, 直到把frequency大于1的那个char扫过.

Time Complexity: O(n). n = s.length().

Space: O(1). 256 map size.

AC Java:

 1 public class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         int res = 0;
 4         int [] map = new int[256];
 5         int count = 0;
 6         int walker = 0;
 7         int runner = 0;
 8         
 9         while(runner < s.length()){
10             if(map[s.charAt(runner++)]++ > 0){
11                 count++;
12             }
13             while(count > 0){
14                 if(map[s.charAt(walker++)]-- > 1){
15                     count--;
16                 }
17             }
18             res = Math.max(res, runner-walker);
19         }
20         return res;
21     }
22 }

上面的方法会跑2*n, 可以只跑n. 需用HashMap来记录每个char和对应index的关系.

遇到repeating char时walker直接走到之前出现这个char的后一位即可.

Time Complexity: O(n). Space: O(n).

AC Java:

 1 public class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         int res = 0;
 4         HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
 5         for(int walker = 0, runner = 0; runner<s.length(); runner++){
 6             char c = s.charAt(runner);
 7             if(hm.containsKey(c)){
 8                 walker = Math.max(walker, hm.get(c));
 9             }
10             res = Math.max(res, runner-walker+1);
11             hm.put(c, runner+1);
12         }
13         return res;
14     }
15 }

跟上Longest Substring with At Most Two Distinct Characters