How To Find The Longest Substring Without Repeating Characters

How To Find The Longest Substring Without Repeating Characters

An example of using a sliding window approach and an unordered map to track character positions

Nhut Nguyen's photo
Nhut Nguyen
·

3 min read

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

One way of checking the repetition of the characters is by using a map to store their indices. For example:

last_visit[s[i]] = i

You might want to find every substring of nonrepeating characters in the string s, then identify the longest one among them.

  1. The character you are checking its repetition and computing the length should be done within its substring;

  2. The map should always update the latest visited index of a character; and

  3. The starting index of a substring is also updated when repetition happens.

Example 1

For the string s = "abcabcbb":

  • When you visit the second letter 'a', the first substring is formed "abc", the next substring starts from the second letter 'a': start = 3 , last_visit['a'] is updated to be 3.

  • When you visit the second letter 'b', its last_visit['b'] is updated to be 4.

  • Repetition is found when you visit the third letter 'b', the second substring "abc" is formed. The next start = 6; last_visit['b'] = 6.

  • The fourth letter 'b' causes a repetition and forms a one-letter substring "b".

  • The string s ends and form another one-letter substring "b".

Code

#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> last_visit;
    int maxLen = 0;
    int start = -1;
    for (int i = 0; i < s.length(); i++) {
        auto it = last_visit.find(s.at(i));
        if (it != last_visit.end()) {
            start = max(start, it->second);
            it->second = i;
        } else {
            last_visit.insert({s.at(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).

Implementation notes

  • You can initialize the start index of the substrings with -1 to deal with the boundary cases.

  • As a best practice, when you check if a map contains a key and retrieve its value, use an iterator and find() like the above solution. DO NOT implement as follow

if (last_visit.find(s.at(i)) != last_visit.end()) {
    start = max(start, last_visit[s.at(i)]);
}

Because the operator [] might perform an additional find().

Thanks for reading. Feel free to share your thought about my content and check out my book10 Classic Coding Challenges for FREE:

C++leetcodeProgramming Blogscodingalgorithms