Katkat
Back

Find longest substring with at most k distinct

SnowflakeSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.