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

For example:

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

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

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.

4. Input: s = "" Output: 0

Implement an algorithm in your chosen language to efficiently determine the length of the longest substring without repeating characters in the given input string. Consider the time and space complexity of your solution. Can you optimize your approach to achieve the best possible performance, especially for very large input strings? What are the edge cases to consider, such as empty strings or strings with only one character?

Longest Substring Without Repeating Characters

Problem Description

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

For example:

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

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

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.

4. Input: s = "" Output: 0

Brute Force Solution

A naive approach would be to generate all possible substrings and check each one for repeating characters. This approach is inefficient but helps to illustrate the problem.

Algorithm

1. Iterate through all possible start indices of the substring.
2. For each start index, iterate through all possible end indices.
3. For each substring, check if it contains repeating characters.
4. If it does not contain repeating characters, update the maximum length if necessary.

Python Code

def length_of_longest_substring_brute_force(s):
    n = len(s)
    max_length = 0
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]
            if len(set(substring)) == len(substring):
                max_length = max(max_length, len(substring))
    return max_length

Example

s = "abcabcbb"
print(length_of_longest_substring_brute_force(s))  # Output: 3

Big(O) Analysis

• Time Complexity: O(n^3) - We have nested loops that iterate through all possible substrings (O(n^2)), and for each substring, we check for repeating characters (O(n)).
• Space Complexity: O(n) - The space is used to store the substring.

Optimal Solution: Sliding Window

A more efficient approach is to use the sliding window technique. We maintain a window of characters and expand it as long as there are no repeating characters. If we encounter a repeating character, we shrink the window from the left until the repeating character is removed.

Algorithm

1. Initialize a set to store the characters in the current window.
2. Initialize two pointers, left and right, to the start of the string.
3. Iterate through the string with the right pointer.
4. If the current character is not in the set, add it to the set and update the maximum length.
5. If the current character is in the set, remove the character at the left pointer from the set and increment the left pointer until the repeating character is removed.
6. Return the maximum length.

Python Code

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    return max_length

Example

s = "abcabcbb"
print(length_of_longest_substring(s))  # Output: 3

s = "bbbbb"
print(length_of_longest_substring(s)) # Output: 1

s = "pwwkew"
print(length_of_longest_substring(s)) # Output: 3

s = ""
print(length_of_longest_substring(s)) # Output: 0

Big(O) Analysis

• Time Complexity: O(n) - The right pointer iterates through the string once, and the left pointer can move at most n times. Therefore, the time complexity is O(n).
• Space Complexity: O(min(m, n)) - The space is used to store the characters in the char_set. In the worst case, the set can contain all the characters in the string (n) or all the characters in the character set (m). Therefore, it's O(min(m,n)).

Edge Cases

• Empty String: If the input string is empty, the algorithm should return 0. The provided solution handles this case correctly.
• String with One Character: If the input string contains only one character, the algorithm should return 1. The provided solution handles this case correctly.
• String with All Same Characters: If the input string contains all the same characters, the algorithm should return 1. The provided solution handles this case correctly.
• String with ASCII characters: The solution works regardless of the set of ASCII characters since it relies on using a Set to track unique characters.