Quick Overview

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.

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.

Overview: 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

  1. Use a sliding window with two pointers (left and right).
  2. Maintain a hash map of character counts within the current window.
  3. When the number of distinct characters exceeds k, move left forward and decrement counts until it is at most k.
  4. Update the best length after reestablishing the constraint.

Loading coding console...

Show the approach

Approach

Use a sliding window with a hash map tracking character frequencies in the current window. Expand the right pointer to include new characters. If the number of distinct characters exceeds k, move the left pointer forward, decrementing counts and removing characters whose count drops to zero, until the window satisfies the constraint again. Track the maximum window length throughout.

Time complexity:
O(n)
Space complexity:
O(min(n, alphabet_size))