# 3. Longest Substring Without Repeating Characters

## Approach 1: Sliding window

• Time: $O(n)$
• Space: $O(128) = O(1)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int lengthOfLongestSubstring(string s) { int ans = 0; vector count(128); for (int l = 0, r = 0; r < s.length(); ++r) { ++count[s[r]]; while (count[s[r]] > 1) --count[s[l++]]; ans = max(ans, r - l + 1); } return ans; } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0; int[] count = new int[128]; for (int l = 0, r = 0; r < s.length(); ++r) { ++count[s.charAt(r)]; while (count[s.charAt(r)] > 1) --count[s.charAt(l++)]; ans = Math.max(ans, r - l + 1); } return ans; } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ans = 0 count = collections.Counter() l = 0 for r, c in enumerate(s): count[c] += 1 while count[c] > 1: count[s[l]] -= 1 l += 1 ans = max(ans, r - l + 1) return ans

## Approach 2: Last seen

• Time: $O(n)$
• Space: $O(128) = O(1)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int lengthOfLongestSubstring(string s) { int ans = 0; int j = -1; // s[j + 1..i] has no repeating chars. vector lastSeen(128, -1); // lastSeen[c] := index of last c appeared. for (int i = 0; i < s.length(); ++i) { // Update j to lastSeen[c], so the window must start from j + 1. j = max(j, lastSeen[s[i]]); ans = max(ans, i - j); lastSeen[s[i]] = i; } return ans; } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int lengthOfLongestSubstring(String s) { int ans = 0; int j = -1; // s[j + 1..i] has no repeating chars. int[] lastSeen = new int[128]; // lastSeen[c] := index of last c appeared. Arrays.fill(lastSeen, -1); for (int i = 0; i < s.length(); ++i) { // Update j to lastSeen[c], so the window must start from j + 1. j = Math.max(j, lastSeen[s.charAt(i)]); ans = Math.max(ans, i - j); lastSeen[s.charAt(i)] = i; } return ans; } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def lengthOfLongestSubstring(self, s: str) -> int: ans = 0 j = -1 # s[j + 1..i] has no repeating chars. lastSeen = {} # lastSeen[c] := index of last c presappearedented. for i, c in enumerate(s): # Update j to lastSeen[c], so the window must start from j + 1. j = max(j, lastSeen.get(c, -1)) ans = max(ans, i - j) lastSeen[c] = i return ans