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

Problem

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 <= 10^5

---

Solution

class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0) return 0;
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++)
            freq[s.charAt(i) - 'a']++;
        boolean flag = true;
        for (int i = 0; i < freq.length; i++)
            if (0 < freq[i] && freq[i] < k) flag = false;
        if (flag == true)
            return s.length();
        int longest = 0;
        int left = 0, right = 0;
        while (right < s.length()) {
            if (freq[s.charAt(right) - 'a'] < k) {
                longest = Math.max(longest, longestSubstring(s.substring(left, right), k));
                left = right + 1;
            }
            right++;
        }
        longest = Math.max(longest, longestSubstring(s.substring(left), k));
        return longest;
    }
}

Explanation

• 문자열이 조건을 만족하는지 알기 위해서는 먼저 문자열의 각 문자가 몇 번 등장하는지 알아야 한다. 문자열 내에서 각 문자가 몇 번 등장하는지 메모하기 위하여 길이가 26(a ~ z)인 배열을 선언하고 각 문자의 개수를 메모한다.

  int[] freq = new int[26];
  for (int i = 0; i < s.length(); i++)
    freq[s.charAt(i) - 'a']++;
  

• 배열 freq를 확인해보면 문자열이 조건을 만족하는지 알 수 있다. 조건 만족 여부를 메모하기 위하여 변수 flag를 선언하고, 배열 freq를 확인하면서 조건을 만족하지 않으면 변수 flag에 false를 할당한다.
• 문자열이 조건을 만족하면 해당 문자열의 길이를 반환하도록 한다.

  boolean flag = true;
  for (int i = 0; i < freq.length; i++)
    if (0 < freq[i] && freq[i] < k) flag = false;
  if (flag == true)
  return s.length();
  

• 문자열을 잘라서 위에 작성한 코드를 모두 적용시켜 조건을 만족하는 가장 긴 문자열을 찾는다.

  int longest = 0;
  int left = 0, right = 0;
  while (right < s.length()) {
    if (freq[s.charAt(right) - 'a'] < k) {
        longest = Math.max(longest, longestSubstring(s.substring(left, right), k));
        left = right + 1;
    }
    right++;
  }
  longest = Math.max(longest, longestSubstring(s.substring(left), k));
  return longest;