# Longest Substring Without Repeating Characters

Medium

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

Example 1:

```Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```

Example 2:

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

Example 3:

```Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
```

Example 4:

```Input: s = ""
Output: 0
```

Constraints:

• `0 <= s.length <= 5 * 104`
• `s` consists of English letters, digits, symbols and spaces.

Approach : Sliding Window

```class Solution {
public int lengthOfLongestSubstring(String s) {

if( s == null || s.isEmpty()){
return 0;
}
int l = 0, r = 0 , max_length = 0;
Set<Character> seen = new HashSet<>();
int n = s.length();
while( r < n){
char cur = s.charAt(r);
if(!seen.contains(cur)){
r++;
max_length = Math.max(max_length, (r-l));
}else{
char to_remove = s.charAt(l);
seen.remove(to_remove);
l++;
}
}
return max_length;
}
}
```

Complexity Analysis

• Time Complexity : `O(2n)=O(n)`. In the worst case each character will be visited twice by i and j.
• Space Complexity : `O(min(m,n))`. Same as the previous approach. We need O(k) space for the sliding window, where k is the size of the `Set`. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m.

Categories: String

Tagged as: ,