3. Longest Substring Without Repeating Characters

LeetCode

My Sol: BruteForce

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int pos = 0;
        int allMax = 0;
        for (int i = 0; i < s.length(); i++){
            int max = 0;
            for (pos = i; pos < s.length(); pos++){
                String sub = s.substring(i, pos);
                String nextChar = s.substring(pos, pos+1);
                if (!sub.contains(nextChar)) {
                    max++;
                } else {
                    break;
                }
            }
            allMax = Math.max(allMax, max);
        }
        return allMax;
    }
}

Remarks:

  1. $O(n^2)$
  2. Java get sub string: s.substring(pos1, pos2)
  3. update max everytime

Updated BF

We can use Set to check duplicates.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int allMax = 0;

        for (int i = 0; i < s.length(); i++) {
            Set<Character> seen = new HashSet<>();
            int max = 0;

            for (int pos = i; pos < s.length(); pos++) {
                char c = s.charAt(pos);
                if (!seen.contains(c)) {
                    seen.add(c);
                    max++;
                } else {
                    break;
                }
            }

            allMax = Math.max(allMax, max);
        }

        return allMax;
    }
}

Remarks:

  1. Still $O(n^2)$
  2. replaced substring and contains with HashSet, which runs faster.

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0, maxLen = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            if (!set.contains(c)) {
                set.add(c);
                right++;
                maxLen = Math.max(maxLen, right - left);
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }

        return maxLen;
    }
}

Remarks:

  1. TC&SC $O(n)$
  2. Control left and right pointers

Better Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] ch = s.toCharArray();
        int[] map = new int[128]; // ASCII range
        int left = 0, right = 0, maxLen = 0;

        while (right < ch.length) {
            if (map[ch[right]] == 0) {
                map[ch[right]] = 1;  // check the symbol
                maxLen = Math.max(maxLen, right - left + 1);
                right++;
            } else {
                map[ch[left]] = 0;   // uncheck
                left++;
            }
        }

        return maxLen;
    }
}

Remarks:

  1. Only works for ASCII (0-127)
  2. Avoids the resource consumption of HashSet calculation
  3. s.charAt(i) checks the string border every-time, which takes more time. Visiting ch[i] is faster than s.charAt(i).