Solving the 'Longest Substring Without Repeating Characters' problem on LeetCode with C++
Tags: leetcode
Published: 2023-06-27 10:19:27

## 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.