Question

Formatted question description: https://leetcode.ca/all/395.html

 395	Longest Substring with At Least K Repeating Characters

 Find the length of the longest substring T of a given string (consists of lowercase letters only)
 such that every character in T appears no less than k times.

 Example 1:

 Input:
 s = "aaabb", k = 3

 Output:
 3
 The longest substring is "aaa", as 'a' is repeated 3 times.

 Example 2:

 Input:
 s = "ababbc", k = 2

 Output:
 5
 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

 @tag-string
 @tag-divideconquer

Algorithm

The idea is divide and conquer.

To find the largest substring of s[i,j], first count the frequency, then traverse the frequency, find the first character whose frequency is less than k and greater than 0, and then find the position of this character,

The next analysis is very important, this character must not appear in any substring,

Because i and j are the entire substring, the frequency in ij does not reach k, so in any substring of ij, this character cannot reach the frequency k.

So there can be no such character, then divide and conquer at this position and return the maximum value of the first half and the second half.

Code

Java

  • public class Longest_Substring_with_At_Least_K_Repeating_Characters {
    
        class Solution {
    
            public int longestSubstring(String str, int k) {
    
                if (str == null || str.length() == 0) {
                    return 0;
                }
    
                char[] s = str.toCharArray();
                int result = 0;
                int n = str.length();
    
                // The maximum number of different letters is only 26. The number of different letters in the substring that meets the meaning of the question must be in the range of [1, 26]
                for (int targetUniqueCount = 1; targetUniqueCount <= 26; targetUniqueCount++) {
    
                    int left = 0;
                    int right = 0;
                    int uniqueCnt = 0; // uniqueCnt to record the number of different letters in the substring
                    int[] countMap = new int[26];
    
                    while (right < n) {
                        if (countMap[s[right++] - 'a']++ == 0) ++uniqueCnt;
                        while (uniqueCnt > targetUniqueCount) {
                            if (--countMap[s[left++] - 'a'] == 0) --uniqueCnt;
                        }
    
                        boolean isValid = true;
                        for (int j = 0; j < 26; ++j) {
                            if (countMap[j] > 0 && countMap[j] < k) isValid = false;
                        }
                        if (isValid) result = Math.max(result, right - left);
                    }
                }
    
                return result;
            }
        }
    
        class Solution_dfs_divide_conquer {
            public int longestSubstring(String s, int k) {
    
                if (s == null || s.length() == 0) {
                    return 0;
                }
    
                return dfs(s, k, 0, s.length() - 1);
            }
    
            private int dfs(String s, int k, int start, int end) {
                if (start > end) { // @note: if ==, will cover in return clause
                    return 0;
                }
    
                int[] count = new int[26];
                for (int i = start; i <= end; i++) {
                    count[s.charAt(i) - 'a']++;
                }
    
                for (int i = 0; i < 26; i++) {
                    if (count[i] > 0 && count[i] < k) { // @note: This character must not appear in any substring
    
                        // indexOf(int ch, int fromIndex)
                        int pos = s.indexOf((char) (i + 'a'), start); // @note: index after start-index
    
                        return Math.max(
                            dfs(s, k, start, pos - 1),
                            dfs(s, k, pos + 1, end)
                        );
                    }
                }
    
                return end - start + 1; // eg. aaabbbccc => not entering if of for loop
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
    // Time: O(N)
    // Space: O(N)
    // Ref: https://discuss.leetcode.com/topic/57134/two-short-c-solutions-3ms-and-6ms
    class Solution {
    private:
        int longestSubstring(string &s, int k, int begin, int end) {
            int cnt[26] = {};
            for (int i = begin; i < end; ++i) cnt[s[i] - 'a']++;
            int i = begin, ans = 0;
            while (i < end) {
                while (i < end && cnt[s[i] - 'a'] < k) ++i;
                int j = i;
                while (j < end && cnt[s[j] - 'a'] >= k) ++j;
                if (i == begin && j == end) return end - begin;
                ans = max(ans, longestSubstring(s, k, i, j));
                i = j;
            }
            return ans;
        }
    public:
        int longestSubstring(string s, int k) {
            return longestSubstring(s, k, 0, s.size());
        }
    };
    
  • class Solution(object):
      def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        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)
    
    

All Problems

All Solutions