# How to solve Leetcode 3. Longest Substring Without Repeating Characters

## An example of using unordered_map in C++

Sep 22, 2022·

### Problem statement

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 a 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 a length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
``````

#### Constraints

• `0 <= s.length <= 5 * 10^4`.

• `s` consists of English letters, digits, symbols and spaces.

### Solution: Store the position of the visited characters

Whenever you meet a visited character `s[i] == s[j]` for some `0 <= i < j < s.length`, the substring `"s[i]...s[j - 1]"` might be valid, i.e. it consist of only nonrepeating characters.

But in case you meet another visited character `s[x] == s[y]` where `x < i < j < y`, the substring `"s[x]...s[y - 1]"` is not valid because it consists of repeated character `s[i] == s[j]`.

That shows the substring `"s[i]...s[j - 1]"` is not always a valid one. You might need to find the right starting position `start >= i` for the valid substring `"s[start]...s[j - 1]"`.

#### Example 4

For the string `s = "babba"`:

• When you visit the second letter `'b'`, the substring `"ba"` is a valid one.

• When you visit the third letter `'b'`, the substring of interest should be started by the second letter `'b'`. It gives you the substring `"b"`.

• When you visit the second letter `'a'`, the substring `"abb"` is not a valid one since `'b'` is repeated. To ensure no repetition, the starting position for this substring should be the latter `'b'`, which leads to the valid substring `"b"`.

• The final longest valid substring is `"ba"` with length 2.

Example 4 shows the starting position `start` for the substring of interest `"s[i]...s[j - 1]"` should be:

``````this_start = max(previous_start, i).
``````

#### Code

``````#include <iostream>
#include <unordered_map>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> position;
int maxLen = 0;
int start = -1;
for (int i = 0; i < s.length(); i++) {
if (position.find(s[i]) != position.end()) {
start = max(start, position[s[i]]);
}
position[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
int main() {
cout << lengthOfLongestSubstring("abcabcbb") << endl;
cout << lengthOfLongestSubstring("bbbbb") << endl;
cout << lengthOfLongestSubstring("pwwkew") << endl;
}
``````
``````Output:
3
1
3
``````

#### Complexity

• Runtime: `O(N)`, where `N = s.length`.

• Extra space: `O(N)`.

### References

Get my FREE book "10 Classic Coding Challenges"