395. Longest Substring with At Least K Repeating Characters

Problem

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

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

Constraints:

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

Problem Summary

Given a string s and an integer k, find the longest substring in s such that every character in this substring appears at least k times. Return the length of this substring.

Solution Ideas

• The easiest approach to think of is recursion. If a certain character appears more than 0 times but fewer than k times, then any substring containing this character does not meet the requirements. Therefore, split the entire string by this character; the longest substring that satisfies the problem must not contain the split character. After splitting, just take the longest substring. Time complexity O(26*n), space complexity O(26^2)
• Another approach for this problem is the sliding window. One issue that needs to be solved is the condition for moving the right window. This problem asks for the longest string, and the final string can contain at most 26 distinct character types. The number of character types is the condition for moving the right window. Enumerate the number of character types in sequence. If the number of character types in the current window is less than the currently enumerated number of character types, move the window to the right; otherwise, move it to the left. During window movement, the freq frequency array needs to be dynamically maintained. You can loop through this array every time to calculate the characters whose occurrence count is greater than k. Although this method loops at most 26 times, it is still not efficient. A more efficient method is to maintain one value, used to record the current number of character types whose occurrence count is less than k, less. If freq is 0, it means the number of character types with fewer than k occurrences is about to change. If the right window moves, then less++; if the left window moves, then less--. Similarly, if freq is k, it means the number of character types with fewer than k occurrences is about to change. If the right window moves, then less--; if the left window moves, then less++. While enumerating the 26 character types, dynamically maintain and record the longest string. After enumeration is complete, the length of the longest string is obtained. Time complexity O(26*n), space complexity O(26)

Code

package leetcode

import "strings"

// Solution 1: Sliding window
func longestSubstring(s string, k int) int {
	res := 0
	for t := 1; t <= 26; t++ {
		freq, total, lessK, left, right := [26]int{}, 0, 0, 0, -1
		for left < len(s) {
			if right+1 < len(s) && total <= t {
				if freq[s[right+1]-'a'] == 0 {
					total++
					lessK++
				}
				freq[s[right+1]-'a']++
				if freq[s[right+1]-'a'] == k {
					lessK--
				}
				right++
			} else {
				if freq[s[left]-'a'] == k {
					lessK++
				}
				freq[s[left]-'a']--
				if freq[s[left]-'a'] == 0 {
					total--
					lessK--
				}
				left++
			}
			if lessK == 0 {
				res = max(res, right-left+1)
			}

		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Solution 2: Recursive divide and conquer
func longestSubstring1(s string, k int) int {
	if s == "" {
		return 0
	}
	freq, split, res := [26]int{}, byte(0), 0
	for _, ch := range s {
		freq[ch-'a']++
	}
	for i, c := range freq[:] {
		if 0 < c && c < k {
			split = 'a' + byte(i)
			break
		}
	}
	if split == 0 {
		return len(s)
	}
	for _, subStr := range strings.Split(s, string(split)) {
		res = max(res, longestSubstring1(subStr, k))
	}
	return res
}