Katkat
Back

Find the Longest Substring with at Most Two Distinct Characters

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests the ability to use the sliding window technique combined with a hash map to maintain a dynamic character set and determine the maximum length of a valid substring in linear time.

Problem Statement

Given a string s, find the length of the longest contiguous substring that contains at most two distinct characters.

If the string is empty, return 0.

Function Signature

def length_of_longest_substring_two_distinct(s: str) -> int:
    pass

Input & Output

  • Input: A string s consisting of printable ASCII characters.
  • Output: An integer representing the length of the longest valid substring.

Examples

Example 1

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which has a length of 3 and contains 2 distinct characters ('e' and 'c').

Example 2

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which has a length of 5 and contains 2 distinct characters ('a' and 'b').

Constraints

  • 0 <= len(s) <= 10^5
  • s consists of standard printable ASCII characters.

Edge Cases to Consider

  • Empty string: s = "" should return 0.
  • Length 1 or 2 strings: The answer is simply len(s).
  • All identical characters: s = "aaaa" should return 4.
  • Alternating characters: s = "abababab" should return 8.

Hints

Hint 1

Consider using a sliding window with two pointers (`left` and `right`) to represent the current candidate substring.

Hint 2

Use a hash map or frequency array to track the occurrences or rightmost indices of characters inside your current window.

Hint 3

Whenever the number of distinct characters in your window exceeds 2, increment `left` and update your counts until only 2 distinct characters remain.

Follow-up questions

  • How would you generalize your solution to find the longest substring with at most k distinct characters?
  • If k is large, how can you optimize the window shrinkage to evict the earliest character in O(1) time?
  • How would you adapt your algorithm if the characters were delivered as an infinite streaming data source rather than a fixed string?