Question

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

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⁴
s consists of only lowercase English letters.
1 <= k <= 10⁵

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

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
        }
    }
}

############

class Solution {
    private String s;
    private int k;

    public int longestSubstring(String s, int k) {
        this.s = s;
        this.k = k;
        return dfs(0, s.length() - 1);
    }

    private int dfs(int l, int r) {
        int[] cnt = new int[26];
        for (int i = l; i <= r; ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        char split = 0;
        for (int i = 0; i < 26; ++i) {
            if (cnt[i] > 0 && cnt[i] < k) {
                split = (char) (i + 'a');
                break;
            }
        }
        if (split == 0) {
            return r - l + 1;
        }
        int i = l;
        int ans = 0;
        while (i <= r) {
            while (i <= r && s.charAt(i) == split) {
                ++i;
            }
            if (i > r) {
                break;
            }
            int j = i;
            while (j <= r && s.charAt(j) != split) {
                ++j;
            }
            int t = dfs(i, j - 1);
            ans = Math.max(ans, t);
            i = j;
        }
        return ans;
    }
}

// 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());
    }
};

'''
>>> s = "ababbc"
>>> set(s)
{'b', 'a', 'c'}

>>> s.count('a')
2
>>> s.count('b')
3

>>> s.split('a')
['', 'b', 'bbc']
'''

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        for c in set(s):
            # no need to try all chars with count<k, get the 1st one and return
            if s.count(c) < k: # @note: This character must not appear in any substring
                return max([self.longestSubstring(t, k) for t in s.split(c)])
        return len(s)

class Solution: # iterative, OJ passed
    def longestSubstring(self, s: str, k: int) -> int:
        n = len(s)
        result = 0
        
        # Iterate over the possible values of unique characters in the substring
        for num_unique in range(1, 27):
            freq_map = [0] * 26
            left = 0
            num_chars = 0
            num_chars_at_least_k = 0
            
            # Sliding window approach to find the longest substring with num_unique characters
            for right in range(n):
                if freq_map[ord(s[right]) - ord('a')] == 0:
                    num_chars += 1
                freq_map[ord(s[right]) - ord('a')] += 1
                if freq_map[ord(s[right]) - ord('a')] == k:
                    num_chars_at_least_k += 1
                
                # Shrink the window if the number of unique characters exceeds num_unique
                while num_chars > num_unique:
                    freq_map[ord(s[left]) - ord('a')] -= 1
                    if freq_map[ord(s[left]) - ord('a')] == k - 1:
                        num_chars_at_least_k -= 1
                    if freq_map[ord(s[left]) - ord('a')] == 0:
                        num_chars -= 1
                    left += 1
                
                # Check if all characters in the substring occur at least k times
                if num_chars == num_chars_at_least_k:
                    result = max(result, right - left + 1)
        
        return result

############

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        def dfs(l, r):
            cnt = Counter(s[l : r + 1])
            split = next((c for c, v in cnt.items() if v < k), '')
            if not split:
                return r - l + 1
            i = l
            ans = 0
            while i <= r:
                while i <= r and s[i] == split:
                    i += 1
                if i >= r:
                    break
                j = i
                while j <= r and s[j] != split:
                    j += 1
                t = dfs(i, j - 1)
                ans = max(ans, t)
                i = j
            return ans

        return dfs(0, len(s) - 1)

func longestSubstring(s string, k int) int {
	var dfs func(l, r int) int
	dfs = func(l, r int) int {
		cnt := [26]int{}
		for i := l; i <= r; i++ {
			cnt[s[i]-'a']++
		}
		var split byte
		for i, v := range cnt {
			if v > 0 && v < k {
				split = byte(i + 'a')
				break
			}
		}
		if split == 0 {
			return r - l + 1
		}
		i := l
		ans := 0
		for i <= r {
			for i <= r && s[i] == split {
				i++
			}
			if i > r {
				break
			}
			j := i
			for j <= r && s[j] != split {
				j++
			}
			t := dfs(i, j-1)
			ans = max(ans, t)
			i = j
		}
		return ans
	}
	return dfs(0, len(s)-1)
}

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

395 - Longest Substring with At Least K Repeating Characters

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions