395. Longest Substring with At Least K Repeating Characters
Hash Table, String, Divide and Conquer, Sliding Window, Review, Memory ·Problem Statement
link: LeetCode.cn LeetCode
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.
if no such substring exists, return 0.
Example:
Input: s = "aaabb", k = 3
Output: 3
Input: s = "ababbc", k = 2
Output: 5
Solution Approach
The solution utilizes a divide and conquer approach to find the longest substring with at least k repeating characters.
Algorithm
- If the length of the input string s is less than k, return 0 as no valid substring can be formed.
- Iterate through each unique character c in the set of s.
- If the count of character c in the string is less than k, split the string at character c and recursively find the longest substring for each split substring.
- Return the maximum length of the substrings obtained from the recursive calls.
Implement
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
if len(s) < k:
return 0
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t,k) for t in s.split(c))
return len(s)