395. Longest Substring with At Least K Repeating C

vvpvvp 发布于2019-08-16 15:09 / 1888人阅读

摘要：题目要求找出字符串中的最长子字符串，满足该子字符串中任何字符出现的次数都大于。思路和代码这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。

题目要求

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.

找出字符串中的最长子字符串，满足该子字符串中任何字符出现的次数都大于k。

思路和代码

这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。反过来想，这个子字符串一定不包含什么元素呢？当一个元素出现的总次数小于k，那么该元素一定不在子字符串中，只需要将其作为分界点，分别找出左半部分和右半部分的满足条件的最长子字符串。

    public int longestSubstring(String s, int k) {
        return longestSubstring(s, k, 0, s.length()-1);
    }
    
    public int longestSubstring(String s, int k, int left, int right) {
        if(left > right) {
            return 0;
        }

        int[] count = new int[26];
        for(int i = left ; i<=right ; i++) {
            count[s.charAt(i) - "a"]++;
        }
        int result = right - left + 1;
        for(int i = left ; i<=right ; i++) {
            if(count[s.charAt(i)-"a"] < k && count[s.charAt(i)-"a"] > 0) {
                int leftLongest = longestSubstring(s, k, left, i-1);
                int rightLongest = longestSubstring(s, k, i+1, right);
                result = Math.max(leftLongest, rightLongest);
                
                break;
            }
        }
        return result;
    }

GPU云服务器云服务器 Repeating least Longest kernel segfault at

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/73311.html

[Leetcode] Longest Substring with At Most 2 Distin

摘要：最新思路解法哈希表法复杂度时间空间思路我们遍历字符串时用一个哈希表，但这个哈希表只记录两个东西，一个字母和它上次出现的时的下标，另一个字母和它上次出现时候的下标。这个通过用哈希表记录字母上次出现的下标，来维护一个窗口的方法也可以用于。 Longest Substring with At Most Two Distinct Characters 最新思路解法：https://yanjia...

imccl 2019-08-14 12:36 评论0 收藏0
[LeetCode] Longest Substring Without Repeating Cha

摘要：建立数组，存储个字符最近一次出现的位置。首次出现某字符时，其位置标记为，并用无重复字符计数器记录无重复字符的长度，再在更新其最大值。循环完整个字符串后，返回最大值。 Problem Given a string, find the length of the longest substring without repeating characters. Examples: Given ...

CoderStudy 2019-08-14 15:48 评论0 收藏0
[Leetcode] Longest Substring Without Repeating Cha

摘要：哈希表是最自然的想法。在遍历字符串时，我们先根据哈希表找出该字符上次出现的位置，如果大于等于子字符串首，便更新子字符串首。结束后，将该字符新的位置放入哈希表中。 Longest Substring Without Repeating Characters 最新更新解法：https://yanjia.me/zh/2018/12/... Given a string, find the ...

FleyX 2019-08-14 12:18 评论0 收藏0
[leetcode] Minimum Window Substring

摘要：使用而不是因为我们需要的是最值，中间值我们不在乎，所以一次收敛到最小。下面来三个需要查重并且记录上次出现的位置，选择以为例，走到用做检查，发现出现过，把移到的下一个。是上个题目的简易版，或者特殊版。这里聊一聊解一类问题，就是满足某一条件的substring最值问题。最开始我们以Minimum Window Substring为例，并整理总结leetcode里所有类似题目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 评论0 收藏0
[Leetcode]Longest Substring Without Repeating Char

摘要：解题思路本题借助实现。如果字符未出现过，则字符，如果字符出现过，则维护上次出现的遍历的起始点。注意点每次都要更新字符的位置最后返回时，一定要考虑到从到字符串末尾都没有遇到重复字符的情况，所欲需要比较下和的大小。 Longest Substring Without Repeating CharactersGiven a string, find the length of the lon...

awesome23 2019-08-16 10:26 评论0 收藏0