2.23 Longest Substring Without Repeating Characters

Description

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.

Method

if we check for each elements as a entry of a substring to find the longest substring, it waste much times because we have do much repeat operations.

I think we can use two pointers to check, if we have meet repeat character. for one pointer, i, it is a low pointer start from 0, and for j, it is a fast pointer, also start from 0

for string "abcacbb" for i 0- > s.length() while (j ->s.length()){ if (meets the repeat){ break; } } len = j - i; max = math.max(len, max); thus the distance from the i to j is the length of the substring without repeat characters, we only need to compare it's length with global variable len; since we make sure in the string (i - (j- 1)) it is a non-repeat substring, while j is the same with one character in the previous substring, we only need to move i foreward to find that repeat character to move it out, then it is a new start of a substring moveout(s[i]); i++; }

Time and Space Complexity

time : o(n) space : o(n)

Code

public class Solution {

   public int lengthOfLongestSubstring(String s) {
       if (s == null || s.length() == 0){
           return 0;
       }
       int[] map = new int[128];
       int max = Integer.MIN_VALUE;

       int i = 0;
       int j = 0;

       while (i < s.length()){
              while (j < s.length()){
                     char c = s.charAt(j);
                     if (map[c] != 0){
                         break;
                     } else {
                         map[c]++;
                         j++;
                     }
              }
              int len = j - i;

              if (len > max){
                  max = len;
              }
              map[s.charAt(i)]--;
              i++;
       }
       return max;
}

}