Find the Longest Substring with at Most Two Distinct Characters

Question

The question asks the candidate to find the longest substring in a given string that contains at most two distinct characters.

Codemia · Accepted Answer

To solve this problem, we can use the sliding window technique. This involves maintaining a window that expands to include characters until we exceed two distinct characters, at which point we will contract the window from the left until we are back to two distinct characters. This allows us to efficiently track the longest valid substring.

1. Initialize two pointers, `left` and `right`, both starting at the beginning of the string.
2. Use a hash map to count the occurrences of characters in the current window.
3. Expand the `right` pointer to include new characters and update the hash map.
4. If the hash map contains more than two distinct characters, increment the `left` pointer to shrink the window until only two distinct characters remain.
5. Keep track of the maximum length of valid substrings found during this process.

The time complexity of this approach is O(n), where n is the length of the string. This is because each character is processed at most twice (once by the `right` pointer and once by the `left` pointer). The space complexity is O(1) since the hash map will contain at most three keys (the two distinct characters and a placeholder).

```python
def longest_substring_two_distinct(s):
    left = 0
    right = 0
    char_count = {}
    max_length = 0

while right < len(s):
        char_count[s[right]] = char_count.get(s[right], 0) + 1

while len(char_count) > 2:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            left += 1

max_length = max(max_length, right - left + 1)
        right += 1

return max_length
```
This code defines a function that implements the sliding window approach to find the longest substring with at most two distinct characters.

Interviewers will be looking for clarity in your explanation of the approach, your ability to write clean and efficient code, and how well you handle edge cases. They will also assess your understanding of time and space complexity, as well as your problem-solving skills under pressure.

Find the Longest Substring with at Most Two Distinct Characters

TikTok

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

TikTok 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