Longest Substring Without Repeating Characters

Question

Given a string, find the length of the longest substring without repeating characters. A classic sliding window problem frequently asked in Meta phone screens.

Codemia · Accepted Answer

The problem requires us to find the length of the longest substring in a given string that does not contain repeating characters. This can be efficiently solved using the sliding window technique, which is applicable here because we need to explore potential substrings dynamically while keeping track of characters seen so far. The sliding window allows us to expand and contract our substring in a linear fashion, making it optimal for this problem.

1. Initialize two pointers, `start` and `end`, both set to 0. `start` will represent the beginning of the current substring, and `end` will represent the current character being examined. 
2. Use a set to keep track of characters in the current substring. 
3. Iterate through the string with the `end` pointer: 
   - If the character at `end` is not in the set, add it to the set and update the maximum length of the substring found. 
   - If the character is in the set, it means we have found a repeating character. Move the `start` pointer to the right until the character at `end` can be added without repetition. 
4. Continue this until the `end` pointer reaches the end of the string. 
5. Return the maximum length found.

**Example**: For the input string 'abcabcbb', the algorithm would proceed as follows: 
- Start with `start = 0`, `end = 0`, and an empty set. 
- Add 'a', 'b', and 'c' to the set while `end` moves to index 3. The maximum length is 3. 
- When `end` points to the second 'a' (index 3), the algorithm moves `start` to index 1 (removing 'a' from the set) and continues until the string is fully processed.

Here is the Python solution implementing the above approach:

```python
def length_of_longest_substring(s: str) -> int:
    char_set = set()
    max_length = 0
    start = 0

for end in range(len(s)):
        while s[end] in char_set:
            char_set.remove(s[start])
            start += 1
        char_set.add(s[end])
        max_length = max(max_length, end - start + 1)

return max_length
```

This code uses a set to track unique characters and dynamically adjusts the start pointer to ensure no characters are repeated in the substring.

The time complexity of this solution is O(n), where n is the length of the string. This is because each character is processed at most twice (once by `end` and once by `start`). The space complexity is O(min(n, m)), where m is the size of the character set (e.g., 26 for lowercase English letters). In the worst case, we may store all characters in the set.

1. **Empty String**: If the input string is empty, the expected output is 0, as there are no characters to form a substring. 
2. **All Unique Characters**: For a string like 'abcdefg', the output is 7, as all characters are unique. 
3. **All Repeating Characters**: For a string like 'aaaaaa', the output is 1, as the longest substring consists of a single character. 
4. **String with Non-Printable Characters**: If the string includes spaces or special characters, they must be treated like any other character, which could affect the substring length.

Longest Substring Without Repeating Characters

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string