Katkat
Back

Find longest substring with ≥k repeats

TikTokSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use the sliding window technique combined with frequency maps to find the longest substring containing characters that each appear at least k times.

Problem Statement

Given a string s and an integer k, write a function to find the length of the longest substring where every character present in that substring appears at least k times.

Function Signature

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

Constraints

  • 1 <= len(s) <= 10^5
  • 1 <= k <= len(s)
  • s consists of lowercase English letters.

Examples

Example 1: Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", where 'a' appears 3 times.

Example 2: Input: s = "ababbc", k = 2 Output: 5 Explanation: The longest substring is "ababb", where 'a' appears 2 times and 'b' appears 3 times.

Edge Cases

  • If no substring satisfies the condition, return 0.
  • If k=1, the answer is the length of the string.
  • String contains only one unique character.

Hints

Hint 1

A sliding window approach can be difficult here because the condition 'at least k' doesn't necessarily shrink monotonically as the window expands.

Hint 2

Consider fixing the number of unique characters allowed in the substring (let's say 'unique_target') and then using a sliding window to find the longest substring with exactly that many unique characters where each appears at least k times.

Hint 3

Since the number of unique characters in the input string is at most 26, you can iterate through all possible values of 'unique_target' from 1 to 26 and calculate the max length for each.

Follow-up questions

  • What is the time complexity of your solution, and can it be optimized if the alphabet size were significantly larger?
  • How would your approach change if we instead wanted to find the longest substring where *at most* one character appears fewer than k times?
  • Can this problem be solved using a divide and conquer approach instead of sliding window? Explain the trade-offs.