Find longest substring with at most k distinct
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given a string s and an integer k, return the length of the longest contiguous substring that contains at most k distinct characters. Provide an O(n) sliding-window algorithm and analyze time and space complexity. Follow-up: modify your approach to also return the substring itself and to correctly handle Unicode grapheme clusters.
Quick Answer: This question evaluates a candidate's ability to design efficient string-processing algorithms using sliding-window techniques, reason about time and space complexity, and correctly handle Unicode grapheme clusters when returning substrings.