395. Longest Substring with At Least K Repeating C

vvpvvp 發布于2019-08-16 15:09 / 1949人閱讀

摘要：題目要求找出字符串中的最長子字符串，滿足該子字符串中任何字符出現的次數都大于。思路和代碼這是一個經典的分治法解決的問題，關鍵在于我們如何將這個問題分解為更小的子問題。

題目要求

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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