 # LeetCode Longest Substring Without Repeating Characters

### Problem statement

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

Problem statement taken from: https://leetcode.com/problems/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``````

Example 3:

``````Input: s = "pwwkew"
Output: 3``````

Example 4:

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

Constraints:

``````- s consists of English letters, digits, symbols and spaces.
- 0 <= s.length <= 5 * 10^4``````

### Explanation

#### Brute force

A brute force solution will be to iterate through all possible substrings of the input string. Let's say we have a function checkUniqueString which returns true or false based on a string that has all unique characters or not.

We generate all possible substrings using two nested for loops and inside which we call checkUniqueString function.

A small code block in C++ will look like this.

``````int n = s.length();

for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
if (checkUniqueString(s, i, j)){
// logic for updating the max length substring
}
}
}``````

checkUniqueString will iterate over the string once to check for any repeating character. Hence it will take O(N) time.

The above two nested for loops will take O(N²) time. The total time complexity is O(N3).

#### Sliding Window

The sliding window approach is widely used in many arrays and string problems. The above brute force approach can be optimized using a sliding window.

A sliding window is a range of elements in the array/string that is defined by start and end indices, i.e., [i, j) (left index included, right index excluded). The window can be used to slide its range in a certain direction. So if we right shift the window to right by 1 element then [i, j) will change to [i + 1, j + 1).

#### Algorithm

Initially, the window size is 0 as we have pointed left and right at the first index. We keep on incrementing right till we find a repeated character in the string. When right finds a repeated character, we found the maximum size of substrings without duplicate characters starting at index left.

We keeping doing for all elements of the string till we reach the end.

``````- Initialize variables left, right, and ans to 0.
- Create an array named as chars of length 128.
This will store the number of times an element appeared in an array.
- Loop while ( right < s.length() )
- set char r = s[right]
- increment chars[r]++
- Loop while ( chars[r] > 1 )
- set char l = s[left]
- decrement chars[l]--
- increment left++
- set maximum till now in ans.
ans = max(ans, right - left + 1)
- increment right++
- return ans``````

The time complexity of the above solution is O(N).

### Optimized sliding window

The above solution can be optimized further. Instead of iterating over each index of the string, we define a mapping of the characters to its index. Then we skip all the characters immediately when we find a repeated character.

#### C++ solution

``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
unordered_map<char, int> map;

for(int i = 0, j = 0; j < s.size(); j++){
if(map.find(s[j]) != map.end()){
i = max(map[s[j]], i);
}
ans = max(ans, j - i + 1);
map[s[j]] = j + 1;
}

return ans;
}
};``````

#### Golang solution

``````func lengthOfLongestSubstring(s string) int {
m := make(map[byte]int)
i, ans := 0, 0

for j := 0; j < len(s); j++ {
if v, ok := m[s[j]]; ok {
if v > i {
i = v
}
}

if j - i + 1 > ans {
ans = j - i + 1
}
m[s[j]] = j + 1
}

return ans
}``````

#### Javascript solution

``````var lengthOfLongestSubstring = function(s) {
var mapping = {};
var i = 0;
var ans = 0;

for(var j = 0; j < s.length; j++){
if(mapping[s[j]]) {
if(mapping[s[j]] > i) {
i = mapping[s[j]];
}
}

if(j - i + 1 > ans){
ans = j - i + 1;
}
mapping[s[j]] = j + 1;
}

return ans;
};``````

Let's dry-run our algorithm to see how the solution works.

``````s = "abcdeafb"
m = map()
ans = 0

Step 1: i = 0, j = 0
s[j] = 'a'
m['a'] = j + 1 = 1
ans = max(ans, j - i + 1) = max(0, 0 - 0 + 1) = 1

Step 2: i = 0, j = 1
s[j] = 'b'
m['b'] = j + 1 = 2
ans = max(ans, j - i + 1) = max(1, 1 - 0 + 1) = 2

Step 3: i = 0, j = 2
s[j] = 'c'
m['c'] = j + 1 = 3
ans = max(ans, j - i + 1) = max(2, 2 - 0 + 1) = 3

Step 4: i = 0, j = 3
s[j] = 'd'
m['d'] = j + 1 = 4
ans = max(ans, j - i + 1) = max(3, 3 - 0 + 1) = 4

Step 5: i = 0, j = 4
s[j] = 'e'
m['e'] = j + 1 = 5
ans = max(ans, j - i + 1) = max(4, 4 - 0 + 1) = 5

Step 6: i = 0, j = 5
s[j] = 'a'
m['a'] is 1
set i = max(i, m['a']) = max(0, 1) = 1
ans = max(ans, j - i + 1) = max(5, 5 - 1 + 1) = 5
m['a'] = 6

Step 7: i = 1, j = 6
s[j] = 'f'
m['f'] = j + 1 = 7
ans = max(ans, j - i + 1) = max(5, 6 - 1 + 1) = 6

Step 8: i = 1, j = 7
s[j] = 'b'
m['b'] is 2
set i = max(i, m['a']) = max(1, 2) = 2
ans = max(ans, j - i + 1) = max(6, 7 - 2 + 1) = 6