Katkat
Back

Design Algorithm for Longest Substring with K Distinct Characters

UpstartData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

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.

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.