algoadvance

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

Clarifying Questions:

1. Is the input string s composed of only ASCII characters?
   • Yes, for simplicity, we assume s is composed of ASCII characters.
2. Can the input string be empty?
   • Yes, and if it is empty, the output should be 0.
3. Should the function consider case sensitivity?
   • Yes, substrings are case-sensitive (e.g., ‘A’ and ‘a’ are different characters).

Strategy:

To solve this problem efficiently, we can use the sliding window technique along with a hash map. The idea is to use two pointers (start and end) to represent the current window, and a variable to track the maximum length found.

1. Initialize a dictionary (char_map) to store the most recent index of each character.
2. Initialize two pointers, start and end, both set to 0, and a variable max_length to 0.
3. Expand the end pointer to iterate through the string:
   • If end character is already in the map and its index is not less than start, update start to be one plus the index of the repeating character.
   • Update the character’s index in the map to the current position of end.
   • Calculate the length of the current window (end - start + 1) and update max_length if it’s greater than the previous max_length.
4. Continue this until end reaches the end of the string.
5. Return max_length.

Code:

def length_of_longest_substring(s: str) -> int:
    char_map = {}
    start = 0
    max_length = 0
    
    for end in range(len(s)):
        if s[end] in char_map and char_map[s[end]] >= start:
            start = char_map[s[end]] + 1
        
        char_map[s[end]] = end
        max_length = max(max_length, end - start + 1)
        
    return max_length

Time Complexity:

• Time Complexity: O(n), where n is the length of the string. Each character is processed at most twice (once in the end pointer and possibly once in the start pointer).
• Space Complexity: O(min(n, m)), where m is the number of possible characters. In the worst case, the dictionary will contain m unique characters, but typically it contains up to n characters of the string.

By using the sliding window approach, we ensure that we check each character in the string only a minimal number of times, making the solution efficient and scalable for longer strings.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?