Longest Substring Without Repeating Characters

Naive Solution: Brute Force

The most straightforward approach is to generate all possible substrings of the input string s and then check each substring to see if it contains only unique characters. We keep track of the longest such substring found.

Algorithm:

1. Iterate through all possible starting positions of the substring (from index 0 to n-1, where n is the length of s).
2. For each starting position, iterate through all possible ending positions (from the starting position to n-1).
3. Extract the substring defined by the starting and ending positions.
4. Check if the substring contains only unique characters. If it does, and its length is greater than the current maximum length, update the maximum length.

Code (Python):

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

Time Complexity: O(n^3). The outer loops iterate in O(n^2) and the substring check takes O(n) in the worst case.

Space Complexity: O(n) in the worst case because set(substring) can store up to n characters.

Optimal Solution: Sliding Window

A more efficient approach is to use the sliding window technique. We maintain a "window" defined by two pointers, left and right. We expand the window to the right until we find a duplicate character. When a duplicate is found, we shrink the window from the left until the duplicate is removed. We continuously update the maximum length of the substring without duplicate characters.

Algorithm:

1. Initialize left and right pointers to 0.
2. Initialize a set (or hash map) to store the characters in the current window.
3. Iterate while right is less than the length of the string.
   • If the character at right is not in the set, add it to the set, increment right, and update the maximum length.
   • If the character at right is already in the set, remove the character at left from the set, and increment left.

Code (Python):

def length_of_longest_substring(s):
    n = len(s)
    left = 0
    right = 0
    max_len = 0
    char_set = set()

    while right < n:
        if s[right] not in char_set:
            char_set.add(s[right])
            max_len = max(max_len, right - left + 1)
            right += 1
        else:
            char_set.remove(s[left])
            left += 1

    return max_len

Time Complexity: O(n). Each pointer (left and right) moves at most n steps.

Space Complexity: O(min(m, n)), where n is the length of the string and m is the size of the character set. In the worst case (all characters are unique), the space complexity is O(n). However, if the character set is small (e.g., ASCII), the space complexity is O(1).

Edge Cases

• Empty string: The code handles this case correctly, returning 0.
• String with only one character: The code handles this case correctly, returning 1.
• String with all same characters: The code handles this case correctly, returning 1.
• String with unique characters: The code handles this case correctly, returning the length of the string.