Show problems as
Classic problem #395MediumHash TableStringDivide and ConquerSliding Window

Longest Substring with At Least K Repeating Characters

Real-world version: Longest Solid Stretch Of The Intake Log
Tracked in this browser only
Read Longest Substring with At Least K Repeating Characters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

An intake log is the lowercase string s, one letter per event, listed in the order the events arrived.

Take any stretch of consecutive events. Call the stretch solid when every letter that occurs anywhere inside it occurs at least k times inside it. Return the length of the longest solid stretch, or 0 when no non-empty stretch is solid.

Examples

Example 1

Input
s = "aaabbbddcaaabbbdd", k = 3
Output
6

The stretch of events 0 through 5 spells aaabbb, where a occurs three times and b occurs three times, so it is solid and its length is 6.

Example 2

Input
s = "abcabc", k = 3
Output
0

Each of a, b and c occurs twice in the whole log, so no letter reaches three occurrences anywhere and no non-empty stretch is solid.

Example 3

Input
s = "aabb", k = 2
Output
4

The whole log holds a twice and b twice, which meets the requirement of at least two occurrences each, so the answer is its full length 4.

Constraints

  • 1 <= s.length <= 10^4
  • s consists of only lowercase English letters.
  • 1 <= k <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def longest_substring(s: str, k: int) -> int:
Java
public int longestSubstring(String s, int k)

More on the same topics