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.

Longest Substring with K Distinct Characters

mediumUpstartData ScientistSliding Window

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.

Examples

Example 1
Input
s = "eceba", k = 2
Output
3
Notes
The longest substring with at most 2 distinct characters is "ece" (length 3).
Example 2
Input
s = "aa", k = 1
Output
2
Notes
The longest substring is "aa" (length 2).

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

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Sample input
{"k":2,"s":"eceba"}
Language
Case 1
Input
{
  "k": 2,
  "s": "eceba"
}
Expected
3
Case 2
Input
{
  "k": 1,
  "s": "aa"
}
Expected
2

Browse More Questions

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))