Design Algorithm for Longest Substring with K Distinct Characters
Company: Upstart
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
Tech interview round 2 – sliding-window algorithm
##### Question
Design an algorithm that finds the length of the longest substring containing at most K distinct characters in a given string.
##### Hints
Maintain left/right pointers and a hash-map of character counts; shrink window when distinct count exceeds K.
Quick Answer: This question evaluates proficiency in string-processing and sliding-window algorithm patterns, assessing competency in designing efficient solutions and managing data structures to track distinct elements and reason about time and space complexity.
Given a string s and an integer k, return the length of the longest contiguous substring that contains at most k distinct characters. If k is 0 or the string is empty, return 0.
Constraints
- 0 <= len(s) <= 200000
- 0 <= k <= len(s)
- Characters are case-sensitive
- Substring must be contiguous
- Aim for O(n) time and O(min(n, alphabet_size)) space
Hints
- Use a sliding window with two pointers (left and right).
- Maintain a hash map of character counts within the current window.
- When the number of distinct characters exceeds k, move left forward and decrement counts until it is at most k.
- Update the best length after reestablishing the constraint.