Longest Substring Without Repeating Characters

Problem

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

Naive Solution

The most straightforward approach is to generate all possible substrings of the given string and then check each substring to see if it contains duplicate characters. If a substring doesn't have repeating characters, we compare its length to the current maximum length found so far.

Code (Python)

def length_of_longest_substring_naive(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

The time complexity for the naive solution is O(n^3), where n is the length of the string. This is because generating all substrings takes O(n^2) time, and checking each substring for duplicates takes O(n) time using the set conversion, resulting in O(n^3).

Space Complexity

The space complexity is O(n) due to storing the substring in the substring variable and the set in set(substring).

Optimal Solution: Sliding Window

A more efficient approach is to use the sliding window technique. The sliding window maintains a window of characters that do not contain any repeating characters. We can use a set or a dictionary to keep track of the characters in the current window.

1. We maintain two pointers, left and right, representing the start and end of the sliding window.
2. We move the right pointer to expand the window.
3. If the character at the right pointer is not in the set, we add it to the set and update the maximum length.
4. If the character at the right pointer is already in the set, we move the left pointer to shrink the window until the repeating character is removed from the set.

Code (Python)

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

Time Complexity

The time complexity for the sliding window solution is O(n), where n is the length of the string. Each character in the string is visited at most twice by the left and right pointers.

Space Complexity

The space complexity is 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, the set can store all the unique characters in the string.

Edge Cases

• Empty String: If the input string is empty, the function should return 0.
• String with all same characters: If the input string contains all same characters (e.g., "bbbbb"), the function should return 1.
• String with unique characters: If the input string contains all unique characters (e.g., "abcdefg"), the function should return the length of the string.