[LeetCode] Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

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.

Approach: Clearly it's a sliding window problem. Like in any other sliding window problem we will maintain start and end indices of current window. We can have a hash map but we can use hash set here as the occurrence of  every character in substring can't be more than one. We will keep incrementing end by 1 and for each index 'end', there could be 2 cases:

1. s[end] is not in current window means it won't be in our hash set too. We can simply add s[end] to hash set i.e. add s[end] to current window. We will also see if the current window length is more than max length then we can assign current length to max length.
2. s[end] is already in current window means it is already in our hash set. In this case we need to slide our window from the left. Means we will keep increasing start index of window and keep removing s[start] from hash set until s[end] character is removed from the hash set / current window.

In the end we will just return the max length. That's all!

Implementation in C#:

    public int LengthOfLongestSubstring(string s)

    {

        int length = s?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        HashSet<char> charSet = new HashSet<char>();

        int start = 0;

        int end = 0;

        int maxLen = 0;

        for ( ; end < length; ++end)

        {

            if (charSet.Contains(s[end]))

            {

                maxLen = Math.Max(maxLen, end - start);

                while (charSet.Contains(s[end]))

                {

                    charSet.Remove(s[start++]);

                }

            }

            charSet.Add(s[end]);

        }

        return Math.Max(maxLen, end - start);

    }

Complexity: O(n)