# Longest Substring Without Repeating Characters

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 the 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 the length of 3.
```

Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

* `s` consists of English letters, digits, symbols and spaces and can be null or empty.

### Solutions

A substring is a contiguous sequence of characters within a string. You need to keep track of the maximum length of the substring found so far. This will be updated as we find longer substrings without repeating characters.

**Approach – Brute Force Technique**

Run two nested loop and keep track of the maximum length of the substring found so far. This will be updated as we find longer substrings without repeating characters.

**Steps**

1. **Initialize maxLength**: The variable `maxLength` is initialized to 0. This variable will keep track of the length of the longest substring without repeating characters that we've found so far.
2. **Check if string is not null**: The algorithm checks if the string `s` is not null. If `s` is null, the function will return `maxLength`, which is 0.
3. **Iterate over the string**: If `s` is not null, the algorithm iterates over each character in the string using a `for` loop, with `i` as the index.
4. **Create a HashSet of characters**: For each character at index `i`, a new HashSet `chars` is created and the character is added to it. A HashSet is a collection of unique elements.
5. **Check for repeating characters**: The algorithm then iterates over the rest of the string starting from `i + 1`. If the current character `s[j]` is already in the HashSet `chars`, it means we've found a repeating character and we break out of the inner loop.
6. **Add non-repeating characters**: If `s[j]` is not in `chars`, it means it's a non-repeating character and it's added to `chars`.
7. **Update maxLength**: After considering each character `s[j]`, the algorithm checks if the number of characters in `chars` (which represents the length of the current substring without repeating characters) is greater than `maxLength`. If it is, `maxLength` is updated to the current substring's length.
8. **Return maxLength**: After the outer loop has finished executing, `maxLength` will hold the length of the longest substring without repeating characters in `s`, and this value is returned.

```csharp
public class Solution
{
    public int LengthOfLongestSubstring(string s)
    {
        int maxLength = 0;

        if (s is not null)
        {
            for (int i = 0; i < s.Length; i++)
            {
                HashSet<char> chars = new HashSet<char>();
                chars.Add(s[i]);
                for (int j = i + 1; j < s.Length; j++)
                {
                    if (chars.Contains(s[j]))
                    {
                        break;
                    }

                    chars.Add(s[j]);
                }

                if (chars.Count > maxLength)
                {
                    maxLength = chars.Count;
                }
            }
        }

        return maxLength;

    }
}
```

> Complexity

* **Time complexity**: `O(N^2)`
* **Space complexity**: `O(N)`

**Approach – Dynamic Sliding Window Technique**

This is a **dynamic sliding window** approach. The term "dynamic" refers to the fact that the window size isn't fixed - it adjusts dynamically based on the conditions of the problem, which in this case is the presence of repeating characters. When a repeating character is found, the window "slides" by moving its start position to the right. This dynamic adjustment of the window size is what makes it a dynamic sliding window approach.

**Steps**

1. **Initialize Variables**: The variables `n`, `set`, `ans`, `i`, and `j` are initialized. `n` is the length of the string `s`. `set` is a HashSet that will store the characters in the current window `[i, j)`. `ans` will store the length of the longest substring without repeating characters. `i` and `j` are pointers representing the start and end of the sliding window, respectively.
2. **Start of Loop**: The `while` loop will continue as long as both `i` and `j` are less than `n`, the length of the string.
3. **Check for Character in Set**: For each iteration of the loop, the algorithm checks if the character at position `j` in the string `s` is in the HashSet `set`.
4. **Character Not in Set**: If the character `s[j]` is not in `set`, it is added to `set` and `j` is incremented by 1. The `ans` variable is then updated to be the maximum of `ans` and the difference between `j` and `i`, which represents the length of the current substring without repeating characters.
5. **Character in Set**: If the character `s[j]` is in `set`, it means we've found a repeating character and we need to move the start of the window to the right. So, the character at position `i` in the string `s` is removed from `set` and `i` is incremented by 1.
6. **Return Maximum Length**: After the loop has finished executing, `ans` will hold the length of the longest substring without repeating characters in `s`, and this value is returned.

```csharp
public class Solution
{
    public int LengthOfLongestSubstring(string s)
    {
        int n = s?.Length ?? -1;
        HashSet<char> set = new HashSet<char>();
        int ans = 0, i = 0, j = 0;

        while (i < n && j < n)
        {
            // Try to extend the range [i, j]
            if (!set.Contains(s[j]))
            {
                // add character into hashset and increment right counter
                set.Add(s[j++]);
                ans = Math.Max(ans, j - i);
            }
            else
            {
                // remove character from hashset and increment left counter
                set.Remove(s[i++]);
            }
        }

        return ans;
    }

}
```

> Complexity

* **Time complexity**: `O(N)`
* **Space complexity**: `O(N)`