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.

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.

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)