395. Longest Substring with At Least K Repeating Characters (Medium)

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

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.

Solutions

class Solution {

    // Traverse the string with a specified window size in which we calculate all the char frequency.

    // Every time you walk forward one step, decrease the frequency of the char excluded from the window
    // and increase the frequency of the char included into the window.

    public int longestSubstring(String s, int k) {
        int ans = 0;

        if (s == null || s.length() < k) {
            return ans;
        }

        int len = s.length();

        if (k <= 1) {
            return len;
        }

        for (int ws = k; ws <= len; ws++) {

            int[] freq = new int[26];
            Arrays.fill(freq, 0);

            // initialize the char frequency in the first window
            for (int i = 0; i < ws; i++) {
                char c = s.charAt(i);
                freq[c - 'a']++;
            }

            // last is the last char in the window
            for (int last = ws - 1; last < len; last++) {
                int c = s.charAt(last);

                // do not add, we should check out the frequency of the first window
                if (last != ws - 1) {
                    char exc = s.charAt(last - ws);
                    char inc = s.charAt(last);

                    freq[exc - 'a']--;
                    freq[inc - 'a']++;
                }

                // if the newly included char meets the requirement, check the whole frequency
                // of current window.
                if (freq[c - 'a'] > 0 && freq[c - 'a'] >= k && check(freq, k)) {
                    // overwrite previous max length
                    ans = ws;
                }
            }
        }

        return ans;
    }

    private boolean check(int[] freq, int k) {

        for (int i = 0; i < freq.length; i++) {

            // exists but the frequency doesn't meet the requirement.

            if (freq[i] > 0 && freq[i] < k) {
                return false;
            }
        }

        return true;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-22 01:55:03

results matching ""

    No results matching ""