LeetCode 395 Longest Substring with At Least K Repeating Characters

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-03-09 10:19:33
    编辑于：2022-03-09 12:38:46
    浏览量：868

概述

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

暴力解

O(n^2) 遍历子串的所有可能起始点和结束点，每次需要 O(n) 的时间复杂度来验证是否 okay，因此最终的时间复杂度为 O(n^3)。

啊不是，我们遍历的时候可以顺手维护的，应该可以 O(1) 验证？

是可以顺手维护，但还是 TLE 了。

class Solution {
public:
    int longestSubstring(string s, int k) {
        int ans = 0;
        for (int i = 0; i < s.size(); i ++) {
            unordered_map<char, int> m;
            int charNum = 0;
            int satisfiedNum = 0;
            for (int j = i; j < s.size(); j ++) {
                m[s[j]] ++;
                if (m[s[j]] == k) {
                    satisfiedNum ++;
                }
                if (m[s[j]] == 1) {
                    charNum ++;
                }
                if (satisfiedNum == charNum) {
                    ans = max(ans, j - i + 1);
                }
            }
        }
        return ans;
    }
};

双指针

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87739/Java-Strict-O(N)-Two-Pointer-Solution

上面的暴力解实际上稍微改改就 O(n) 了。

首先原问题中没有限定子串里要有几个 unique 字符，如果限定了就好办了。

限定了之后，我们就可以 O(n) 遍历，当不够时推进右边界，当多余或相同时推进左边界。

目标解必然是 1~26 个 unique 字符中的一种清空，此时只需要遍历这 26 种 case 就好。

总的时间复杂度依然是 O(n)。

public class Solution {
    public int longestSubstring(String s, int k) {
        char[] str = s.toCharArray();
        int[] counts = new int[26];
        int h, i, j, idx, max = 0, unique, noLessThanK;
        
        for (h = 1; h <= 26; h++) {
            Arrays.fill(counts, 0);
            i = 0; 
            j = 0;
            unique = 0;
            noLessThanK = 0;
            while (j < str.length) {
                if (unique <= h) {
                    idx = str[j] - 'a';
                    if (counts[idx] == 0)
                        unique++;
                    counts[idx]++;
                    if (counts[idx] == k)
                        noLessThanK++;
                    j++;
                }
                else {
                    idx = str[i] - 'a';
                    if (counts[idx] == k)
                        noLessThanK--;
                    counts[idx]--;
                    if (counts[idx] == 0)
                        unique--;
                    i++;
                }
                if (unique == h && unique == noLessThanK)
                    max = Math.max(j - i, max);
            }
        }
        
        return max;
    }
}

递归法

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87736/C%2B%2B-recursive-solution

基本的想法是，统计所给区间内所有字符的出现次数，找到一个小于出现次数 k 的字符，则该字符可以把问题拆分成两个部分（因为最终解必然不包含该字符）。当然如果找不到的话说明 okay。

时间复杂度 O(n^2)？

class Solution {
public:
    int longestSubstring(string s, int k) {
        unordered_map<char, int> m;
        for (auto c : s) m[c] ++;
        int i = 0;
        while (i < s.size() && m[s[i]] >= k) i ++;
        if (i == s.size()) return s.size();
        else return max(longestSubstring(s.substr(0, i), k), longestSubstring(s.substr(i+1), k));
    }
};

动态规划法

这里有重复子问题吗？考虑到我们要记录每个字符的当前出现次数，我感觉应该不能用动态规划欸。

Links: leetcode-395-longest-substring-with-at-least-k-repeating-characters