Sliding Window on string

Question

Given a string, implement a sliding window algorithm to find the length of the longest substring without repeating characters. The function should take a string as input and return an integer representing the length of the longest substring.

Codemia · Accepted Answer

The problem requires us to find the length of the longest substring without repeating characters in a given string. This problem can be effectively solved using the sliding window technique combined with a hash map (or dictionary) to track the last index of each character. The sliding window approach allows us to maintain a dynamic window of characters that we are currently considering as a valid substring, and we can expand or shrink this window based on whether we encounter repeating characters.

1. Initialize two pointers, `left` and `right`, both set to the start of the string, and a variable `max_length` to store the maximum length of substring found.  
2. Create a hash map to keep track of the characters and their most recent indexes.  
3. Iterate through the string with the `right` pointer:  
   - If the character at `right` is already in the hash map and its index is greater than or equal to `left`, it means we have a repeating character. We then update `left` to be one more than the last index of that character to avoid counting the duplicate.  
   - Update the hash map with the current character's index.  
   - Calculate the current length of the substring as `right - left + 1`, and update `max_length` if this length is greater than the previously recorded maximum.  
4. Continue this until the `right` pointer reaches the end of the string.  
5. Return `max_length` as the result.

```python
def length_of_longest_substring(s: str) -> int:
    char_index_map = {}
    left = 0
    max_length = 0

for right in range(len(s)):
        if s[right] in char_index_map and char_index_map[s[right]] >= left:
            left = char_index_map[s[right]] + 1
        char_index_map[s[right]] = right
        max_length = max(max_length, right - left + 1)

return max_length
```

The time complexity of this solution is O(n), where n is the length of the input string. This is because both the `left` and `right` pointers traverse the string at most once in a linear fashion. The space complexity is O(min(n, m)), where m is the size of the character set (e.g., 26 for lowercase letters). In the worst case, we might store every character in the hash map, but this depends on the unique character count.

1. Empty string: The function should return 0 since there are no characters.  
2. String of length 1: The function should return 1, as there is only one character.  
3. All characters are the same: For input like 'aaaa', the output should be 1.  
4. Long string with no repeats: For input like 'abcdefg', the output should be the length of the string itself.  
5. Mixed characters: Strings with spaces, punctuation, or numbers should also be handled correctly, treating each unique character as valid.

Sliding Window on string

Grafana Labs

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Grafana Labs Machine Learning 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