Solving the 'Longest Substring Without Repeating Characters' problem on LeetCode with C++

Problem

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Answer

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

        for (int right = 0; right < s.length(); right++) {
            if (map.find(s[right]) != map.end()) {
                left = std::max(left, map[s[right]] + 1);
            }

            map[s[right]] = right;
            maxLength = std::max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

Let's consider the solution to this problem.

The answer is 4 (sapd) when the input is asapda.
We will examine a character from the beginning.
When the first a appears, the length of the longest
substring is 1 (a).

Next, s appears for the first time, extending the length of the longest substring to 2 (as).
Then a appears for the second time. As a already appeared at the beginning of the string, we can't include it in the count.

We are tasked with finding the length of the longest substring without repeating characters. asa would not be the correct answer.

Next we have to start counting characters from the position of s.
This implies that if we encounter a character for the second time, we should start counting from the character following the first occurrence of that character.

Next, p appears for the first time, extending the length of the longest substring to 3 (sap).

Next, d also appears for the first time, extending the length of the longest substring to 4 (sapd).
Last, a appears for the second time, we don't count it.

So the answer is 4 (sapd).

Now, let's consider the above solution in terms of code.
The crucial point is that when a character reappears, we must start counting from the next character in the position in which it last appeared.

We will store the index of a character when we encounter it.
For example with asapda, a is at index 0, s is at index 1.

When a reappears, we need to start counting from the next index after the first a and update the index of a with the new a index.
We don't need to store the index of the same character more than once.

A Map is suitable for this problem because it allows us to store unique key-value pairs. We store a character as the key and its index as the value.

We need to have two variables: the first variable indicates where to start counting and the second variable indicates where to finish counting.

Let's consider the answer code in detail.

        std::unordered_map<char, int> map;
        int maxLength = 0;
        int left = 0;

We declare map as a Map data structure to store a character as the key and its index as the value. The maxLength variable counts the length of the longest substring, and the left variable is indicating where to start counting.

        for (int right = 0; right < s.length(); right++) {

The right variable is that counts characters forward.

            if (map.find(s[right]) != map.end()) {
                left = std::max(left, map[s[right]] + 1);
            }

If we encounter the same character for the second time, we update left, which is the position where we start counting.

However left must not go back from its current position, reassign left to the greater of the current left and the original left.

            map[s[right]] = right;
            maxLength = std::max(maxLength, right - left + 1);
        }

map[s[right]] = right stores a character as the key and its index as the value.

std::max(maxLength, right - left + 1) updates maxLength with the larger of the current maxLength or right (the forward counter) minus left (the start counting position).

We add 1 to ensure accurate character counting because index start from 0.