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:

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.

2. Implementation

(1) Two Pointers + Hash

思路: 由于题目说了string只包含lowercase的字母，所以我们可以列举包含1个字母到包含全部26个字母情况下，找出满足条件的最长子串.其中unique代表不同的字母个数，atLeastK代表在子串中重复出现的次数至少k次的字母的个数

class Solution {
    public int longestSubstring(String s, int k) {
        int[] map = new int[256];
        int start = 0, end = 0, unique = 0, atLeastK = 0;
        int maxLen = 0;

        for (int target = 1; target <= 26; target++) {
            Arrays.fill(map, 0);
            start = 0;
            end = 0;
            unique = 0;
            atLeastK = 0;

            while (end < s.length()) {
                if (map[s.charAt(end)] == 0) {
                    ++unique;
                }

                if (map[s.charAt(end)] == k - 1) {
                    ++atLeastK;
                }

                ++map[s.charAt(end)];
                ++end;

                while (unique > target) {
                    if (map[s.charAt(start)] == k) {
                        --atLeastK;
                    }

                    if (map[s.charAt(start)] ==  1) {
                        --unique;
                    }
                    --map[s.charAt(start)];
                    ++start;
                }

                // 当子串中不同字母的个数等于target，且所以这些不同的字母至少出现k次，更新maxLen
                if (unique == target && atLeastK == unique) {
                    maxLen = Math.max(maxLen, end - start);
                }
            }
        }
        return maxLen;
    }
}

(2) Divide and Conquer

class Solution {
    public int longestSubstring(String s, int k) {
        return findLongestSubstring(s, k, 0, s.length() - 1);
    }

    public int findLongestSubstring(String s, int k, int start, int end) {
        if (start > end || end - start + 1 < k) {
            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) {
                int index = s.indexOf((char)(i + 'a'), start);

                return Math.max(findLongestSubstring(s, k, start, index - 1), findLongestSubstring(s, k, index + 1, end));
            }
        }
        return end - start + 1;
    }
}

3. Time & Space Complexity

Two Pointers + Hash: 时间复杂度O(26 * n), 空间复杂度O(1)

Divide and Conquer: 时间复杂度O(n^2), 空间复杂度O(n)