Longest Substring Without Repeating Characters

, , , , , ,

Question

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

Example

1
2
3
4
5
6
7
8
9
10
11
12
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

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

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.

Solution

Using Sliding Window and set the start and end pointer. When we move the end pointer, increase the value and when the value is greater than 1, we have to move the start pointer to try to reduce the value.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// time:O(n)
// space:O(256) ~ O(1)
public int lengthOfLongestSubstring(String s) {
       if (s == null || s.length() == 0) return 0;
       int[] counter = new int[256];
       int start = 0, end = 0;
       int res = 0;
       while (end < s.length()) {
           counter[s.charAt(end)]++;
           // once exists repeat characters, we have to move start pointer to reduce the value of repeated character.
           while (counter[s.charAt(end)] > 1) {
               counter[s.charAt(start)]--;
               start++;
           }
           res = Math.max(res, end + 1 - start);
           end++;
       }
       return res;
   }