LeetCode 395. Longest Substring with At Least K Repeating Characters

Post by ailswan Dec. 13, 2023

395. Longest Substring with At Least K Repeating Characters

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

  1. If the length of the input string s is less than k, return 0 as no valid substring can be formed.
  2. Iterate through each unique character c in the set of s.
  3. 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.
  4. 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)