Katkat
Back

Solve common string/DP/stack problems

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to identify and implement an efficient solution for finding the longest substring that satisfies specific constraints, requiring a sliding window approach.

Problem: Longest Substring with at most K Distinct Characters

Given a string s and an integer k, write a function to find the length of the longest substring that contains at most k distinct characters.

Function Signature

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:

Constraints

  • 0 <= s.length <= 5 * 10^4
  • 0 <= k <= 50

Examples

Example 1: Input: s = "eceba", k = 2 Output: 3 Explanation: The substring is "ece" with length 3.

Example 2: Input: s = "aa", k = 1 Output: 2 Explanation: The substring is "aa" with length 2.

Edge Cases

  • If k is 0, the longest substring length is 0.
  • If the length of the string is less than or equal to k, the answer is the length of the string.

Requirements

  • The solution should have a time complexity of O(n) and a space complexity of O(k).

Hints

Hint 1

Consider using a sliding window defined by two pointers, `left` and `right`, to represent the current substring.

Hint 2

Maintain a hash map or a frequency array to keep track of the count of distinct characters currently present in the window.

Hint 3

When the number of distinct characters in the map exceeds `k`, shrink the window from the left until the count of distinct characters is back to `k`.

Follow-up questions

  • How would you modify the solution if you needed to return the actual substring instead of just its length?
  • What changes would be required if the constraint was 'exactly k' distinct characters instead of 'at most k'?
  • How would you adapt this approach to handle an infinite stream of characters where you cannot store the entire string in memory?