Skip to content

395. Longest Substring with At Least K Repeating Characters

Description

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 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 <= 104
  • s consists of only lowercase English letters.
  • 1 <= k <= 105

Solutions

Solution 1

Thinking

Longest substring in which every present character occurs at least \(k\) times. A distinct-count window does not capture “all \(\ge k\)”. A character that appears fewer than \(k\) times in the whole range cannot appear in any legal substring, so it is a split point.

Count the range, split on a rare character, and recurse; if none exists the range is legal. Depth is at most \(26\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int longestSubstring(string s, int k) {
        function<int(int, int)> dfs = [&](int l, int r) -> int {
            int cnt[26] = {0};
            for (int i = l; i <= r; ++i) {
                cnt[s[i] - 'a']++;
            }
            char split = 0;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > 0 && cnt[i] < k) {
                    split = 'a' + i;
                    break;
                }
            }
            if (split == 0) {
                return r - l + 1;
            }
            int i = l;
            int ans = 0;
            while (i <= r) {
                while (i <= r && s[i] == split) {
                    ++i;
                }
                if (i >= r) {
                    break;
                }
                int j = i;
                while (j <= r && s[j] != split) {
                    ++j;
                }
                int t = dfs(i, j - 1);
                ans = max(ans, t);
                i = j;
            }
            return ans;
        };
        return dfs(0, s.size() - 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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)
}

Comments