[Leetcode] 395. Longest Substring with At Least K Repeating Characters

문제)

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

 

Example 1:

Input: s = "aaabb", k = 3 Output: 3 Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2 Output: 5 Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

 

Constraints:

• 1 <= s.length <= 104
• s consists of only lowercase English letters.
• 1 <= k <= 105

 

풀이)

1. Brute Force

    public int longestSubstring(String s, int k) {
        if (s == null || s.isEmpty() || k > s.length()) {
            return 0;
        }
        int[] countMap = new int[26];
        int n = s.length();
        int result = 0;
        for (int start = 0; start < n; start++) {
            // reset the count map
            Arrays.fill(countMap, 0);
            for (int end = start; end < n; end++) {
                countMap[s.charAt(end) - 'a']++;
                if (isValid(s, start, end, k, countMap)) {
                    result = Math.max(result, end - start + 1);
                }
            }
        }
        return result;
    }

    private boolean isValid(String s, int start, int end, int k, int[] countMap) {
        int countLetters = 0, countAtLeastK = 0;
        for (int freq : countMap) {
            if (freq > 0) countLetters++;
            if (freq >= k) countAtLeastK++;
        }
        return countAtLeastK == countLetters;
    }

1) Intuition

가능한 모든 경우의 수를 만들어보고, 주어진 조건을 만족하는지 확인. 그리고 주어진 조건을 만족하는 substring에서 가장 긴 substring 리턴

 

2) Algorithm

 - start, end를 기준으로 substring을 만든다.

 - substring의 각 문자가 몇 번 나왔는지 countMap에 저장

 - inValide함수를 통해 모든 문자가 적어도 k번 등장했는지 체크한다.

 - 최대값 리턴

 

3) 시간복잡도

O(26 * n²) : string의 모든 substring 경우의 수 * countMap array size 26

=> O(n²)

 

2. Divide And Conquer

    public int longestSubstring(String s, int k) {
        return longestSubstringUtil(s, 0, s.length(), k);
    }

    int longestSubstringUtil(String s, int start, int end, int k) {
        if (end < k) return 0;
        int[] countMap = new int[26];
        // update the countMap with the count of each character
        for (int i = start; i < end; i++)
            countMap[s.charAt(i) - 'a']++;
        for (int mid = start; mid < end; mid++) {
            if (countMap[s.charAt(mid) - 'a'] >= k) continue;
            int midNext = mid + 1;
            while (midNext < end && countMap[s.charAt(midNext) - 'a'] < k) midNext++;
            return Math.max(longestSubstringUtil(s, start, mid, k),
                    longestSubstringUtil(s, midNext, end, k));
        }
        return (end - start);
    }

1) Intuition

 재귀로 string을 substring으로 쪼갠 후(divide), 주어진 조건을 만족하는 substring을 찾기 위해 각 결과를 하나로 합친다(conquer). 역시나 start와 end를 기준으로 가장 긴 substring을 찾아내는 방식. string은 invalid 문자를 기준으로 쪼개면 된다.

 

2) Algorithm

 - 각 문자의 갯수를 카운트 할 countMap을 만든다.

 - string을 순회하며 mid 값을 찾는다. (참고로, mid는 string의 첫번째 invalid 문자임)

 - 재귀로 결과를 찾는다.

 

3) 시간복잡도

O(n²)