LeetCode Top Interview Questions 395. Longest Substring with At Least K Repeating Characters (Medium

柔情只为你懂 2023-07-03 02:38 23阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 395. Longest Substring with At Least K Repeating Characters (Java版; Meidum) ##

#### 题目描述 ####

Find the length of the longest substring T of a given string (consists of lowercase letters only) 
    such that every character in T appears no less than k times.
    
    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.

#### 第一次做; 直接借鉴了题解的思想, 使用递归处理 ####

/* 我需要知道子串中每个字符出现的次数 借助哈希表可以实现O(N^2)的解法 怎样知道字串中所有字符的出现次数都大于等于k次, 可以借助一个boolean数组实现, 初始化全是true 不满足出现次数要求的元素对应的值是false, 然后验证状态时对数组所有的元素进行&操作; 不需要用boolean数组, 直接用一个整数即可, 一个整数32位, 只用其中的26位就够了 双指针+哈希+位操作 时间复杂度O(N), 空间复杂度O(1) 什么时候移动左右指针? 先移动右指针, 直到满足条件, 然后再移动 */
    class Solution { 
        public int longestSubstring(String s, int k) { 
            char[] chs = s.toCharArray();
            return core(chs, k, 0, s.length()-1);
        }
        //递归函数逻辑: 检查[left,right]范围上满足条件的最长子串
        public int core(char[] chs, int k, int left, int right){ 
            //base case: [left,right]的长度必须大于等于k, 否则返回0
            if(right-left+1<k)
                return 0;
            //对于每个[left,right]都需要单独统计该范围上各个字符出现的次数
            int[] arr = new int[26];
            //统计[left,right]范围上每个字符出现的次数
            for(int i=left; i<=right; i++){ 
                arr[chs[i]-'a']++;
            }
            //优化,缩小判断范围
            for(int i=left; i<=right && right-left>=k; i++){ 
                if(arr[chs[i]-'a']<k)
                    left=i+1;
                else
                    break;
            }
            for(int j=right; j>=left && right-left>=k; j--){ 
                if(arr[chs[j]-'a']<k)
                    right=j-1;
                else
                    break;
            }
            //优化,缩小判断范围
            
            int max = 0;
            for(int i=left; i<=right; i++){ 
                if(arr[chs[i]-'a']<k){ 
                    //新条件新递归
                    max = Math.max(core(chs,k,left,i-1), core(chs,k,i+1,right));
                    //最核心: 在这里直接返回! 相当于如果遇到了一个出现次数少于k的字符, 那么以这个字符为分界, 获取分界线两侧的结果, 然后返回, 不再处理原始的[left,right]
                    return max;
                }
            }
            //执行到这里,说明[left,right]满足条件
            return right-left+1;
        }
    }

#### 未完成的双指针想法 ####

#### [力扣优秀题解][Link 1] ####

class Solution { 
        public int longestSubstring(String s, int k) { 
            int len = s.length();
            if (len == 0 || k > len) return 0;
            if (k < 2) return len;
    
            return count(s.toCharArray(), k, 0, len - 1);
        }
    
        private static int count(char[] chars, int k, int p1, int p2) { 
            if (p2 - p1 + 1 < k) return 0;
            int[] times = new int[26];  // 26个字母
            // 统计出现频次
            for (int i = p1; i <= p2; ++i) { 
                ++times[chars[i] - 'a'];
            }
            // 如果该字符出现频次小于k，则不可能出现在结果子串中
            // 分别排除，然后挪动两个指针
            while (p2 - p1 + 1 >= k && times[chars[p1] - 'a'] < k) { 
                ++p1;
            }
            while (p2 - p1 + 1 >= k && times[chars[p2] - 'a'] < k) { 
                --p2;
            }
    
            if (p2 - p1 + 1 < k) return 0;
            // 得到临时子串，再递归处理
            for (int i = p1; i <= p2; ++i) { 
                // 如果第i个不符合要求，切分成左右两段分别递归求得
                if (times[chars[i] - 'a'] < k) { 
                    return Math.max(count(chars, k, p1, i - 1), count(chars, k, i + 1, p2));
                }
            }
            return p2 - p1 + 1;
        }
    }

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/solution/javadi-gui-by-tzfun/