Katkat
Back

Find longest substring with at least k repeats

C3 AIData Scientist · Technical Screen
HardData ScientistTechnical ScreenCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find longest substring with at least k repeats states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Find longest substring with at least k repeats

Longest substring where each character appears at least k times

You are given:

  • a string s consisting of lowercase English letters
  • an integer k

Return the length of the longest substring of s such that every distinct character in that substring appears at least k times within the substring.

If no such substring exists, return -1.

Notes / assumptions

  • A substring is contiguous.
  • If k <= 1, the answer is len(s).
  • You should handle edge cases like empty string, k > len(s), and repeated characters.

Example

  • s = "aaabb", k = 3 → longest valid substring is "aaa" → return 3.

Clarifying Questions to Ask

  • Clarify input sizes, value ranges, mutability, return format, and tie-breaking.
  • State the target time and space complexity before coding.
  • Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes.

Follow-up questions

  • How would the approach change if the input were streaming or too large for memory?
  • What invariants would you assert in production code?
  • Which tests would catch off-by-one, duplicate, or tie-breaking bugs?