Description Total Accepted: 283937 Total Submissions: 1178327 Difficulty: Medium Contributor: LeetCode Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, 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.

Hide Company Tags Amazon Adobe Bloomberg Yelp Hide Tags Hash Table Two Pointers String Hide Similar Problems (H) Longest Substring with At Most Two Distinct Characters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


package string;

public class LengthOfLongestSubstring {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
      String[] tests = {"ctnlk", "z", "aaaa", "aab", "", "an++--viaj"};
      int[] res = {5, 1, 1, 2, 0, 5};
      for (int i = 0; i < tests.length; i++) {
    	  int ans = lengthOfLongestSubstring(tests[i]); 
    	  System.out.println(ans == res[i]);
      }
	}
	
	public static int lengthOfLongestSubstring(String s) {
	  int[] map = new int[256]; // map from character's ASCII to its last occured index
	  int j = 0;
	  int len = 0;
	  for (int i = 0; i < s.length(); i++) {
		  while (j < s.length() && map[s.charAt(j)] == 0) {
			  map[s.charAt(j)] = 1;					  
			  len = Math.max(len,  j - i + 1);
			  j++;
		  }
		  map[s.charAt(i)] = 0;
	  }
	  return len;
	}
	
	
    public static int lengthOfLongestSubstring_failed(String s) {
        if (s == null || s.length() == 0 || s.length() == 1) return s.length();
        int len = 0;
        char[] arr = s.toCharArray();
        
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
        	    while (j < s.length()) {
	              if(j < s.length() && arr[i] != arr[j]) {
	            	// System.out.printf("arr[%d] = %c \t", j, arr[j]);
	                len = Math.max(len, j - i + 1);
	                j++;
	              } 
	              if (j < s.length() && arr[i] == arr[j]) {
	                len = Math.max(len, j - i );
	                i = j;
	                j++;
	              }              
	            }
        	}
        
        return len;
    }
}