395 Longest Substring with At Least K Repeating Characters

395. Longest Substring with At Least K Repeating Characters​
1. Question
Find the length of the longest substringTof a given string (consists of lowercase letters only) such that every character inTappears no less thanktimes.
Example 1:
1
Input: s = "aaabb", k = 3
2
​
3
Output: 3
4
​
5
The longest substring is "aaa", as 'a' is repeated 3 times.
Copied!
Example 2:
1
Input: s = "ababbc", k = 2
2
​
3
Output: 5
4
​
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
Copied!
2. Implementation
(1) Two Pointers + Hash
思路: 由于题目说了string只包含lowercase的字母，所以我们可以列举包含1个字母到包含全部26个字母情况下，找出满足条件的最长子串.其中unique代表不同的字母个数，atLeastK代表在子串中重复出现的次数至少k次的字母的个数
1
class Solution {
2
    public int longestSubstring(String s, int k) {
3
        int[] map = new int[256];
4
        int start = 0, end = 0, unique = 0, atLeastK = 0;
5
        int maxLen = 0;
6
​
7
        for (int target = 1; target <= 26; target++) {
8
            Arrays.fill(map, 0);
9
            start = 0;
10
            end = 0;
11
            unique = 0;
12
            atLeastK = 0;
13
​
14
            while (end < s.length()) {
15
                if (map[s.charAt(end)] == 0) {
16
                    ++unique;
17
                }
18
​
19
                if (map[s.charAt(end)] == k - 1) {
20
                    ++atLeastK;
21
                }
22
​
23
                ++map[s.charAt(end)];
24
                ++end;
25
​
26
                while (unique > target) {
27
                    if (map[s.charAt(start)] == k) {
28
                        --atLeastK;
29
                    }
30
​
31
                    if (map[s.charAt(start)] ==  1) {
32
                        --unique;
33
                    }
34
                    --map[s.charAt(start)];
35
                    ++start;
36
                }
37
​
38
                // 当子串中不同字母的个数等于target，且所以这些不同的字母至少出现k次，更新maxLen
39
                if (unique == target && atLeastK == unique) {
40
                    maxLen = Math.max(maxLen, end - start);
41
                }
42
            }
43
        }
44
        return maxLen;
45
    }
46
}
Copied!
(2) Divide and Conquer
1
class Solution {
2
    public int longestSubstring(String s, int k) {
3
        return findLongestSubstring(s, k, 0, s.length() - 1);
4
    }
5
​
6
    public int findLongestSubstring(String s, int k, int start, int end) {
7
        if (start > end || end - start + 1 < k) {
8
            return 0;
9
        }
10
​
11
        int[] count = new int[26];
12
        for (int i = start; i <= end; i++) {
13
            ++count[s.charAt(i) - 'a'];
14
        }
15
​
16
        for (int i = 0; i < 26; i++) {
17
            if (count[i] > 0 && count[i] < k) {
18
                int index = s.indexOf((char)(i + 'a'), start);
19
​
20
                return Math.max(findLongestSubstring(s, k, start, index - 1), findLongestSubstring(s, k, index + 1, end));
21
            }
22
        }
23
        return end - start + 1;
24
    }
25
}
Copied!
3. Time & Space Complexity
Two Pointers + Hash: 时间复杂度O(26 * n), 空间复杂度O(1)
Divide and Conquer: 时间复杂度O(n^2), 空间复杂度O(n)

360 Sort Transformed Array

424 Longest Repeating Character Replacement

Last modified 2yr ago

Copy link

Contents

395. Longest Substring with At Least K Repeating Characters

1. Question

2. Implementation

3. Time & Space Complexity

395. Longest Substring with At Least K Repeating Characters​

1. Question

2. Implementation

3. Time & Space Complexity

395. Longest Substring with At Least K Repeating Characters