[leetcode 395] 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.

 

문자열이 최소 k번 등장하는 가장 긴 부분 문자열 찾기

 

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.

 

접근 방법:

브루트포스는 tle

1. 재귀사용

리트코드 솔루션 참고

문자열 ababcabaadc를 보자. k=2이다.

가장 긴 문자열을 파괴하는 알파벳은 한 개밖에 없는 d이다. 이제 d를 기준으로 문자 앞뒤를 잘라서 다시 긴 문자열을 따진다.

 

일반화하자면,

문자열을 구간별로 돌면서 조건을 파괴하는 문자를 기준으로 앞뒤를 자른다. (next = mid+1)

 

앞뒤를 기준으로 다시 가장 긴 문자열을 리턴한다. (return max(recur(start, mid), recur(next, end))

 

문자열 구간이 모두 조건을 만족한다면 return end-start를 할것이고 그게 아니라면 계속 문자가 앞뒤로 divide 될 것이다. 

class Solution {
    
    public int recursive(String s, int start, int end, int k){
        
        if(end < k) return 0;
        
        int[] count = new int[26];
        
        for(int i=start; i<end; i++){
            count[s.charAt(i)- 'a']++;
        }
        
        for(int mid = start; mid<end; mid++){
            if(count[s.charAt(mid) - 'a'] >= k) continue;
            
            int next = mid + 1;
            while(next < end && count[s.charAt(next) - 'a'] < k) next++;
            
            return Math.max(recursive(s, start, mid, k), recursive(s, next, end, k));
        }
        
        return end - start;
    }
    
    public int longestSubstring(String s, int k) {
        
        int n = s.length();
        
        return recursive(s, 0, n, k);
    }
}

 

 

2. 투포인터(슬라이딩 윈도우) 사용

 

리트코드 솔루션 참고

문자열 전체에서 unique 알파벳수를 센다.

start, end사이에서 문자열을 구성하고 있는 알파벳수를 기준으로 가장 긴 문자열 구간을 체크한다.

 

class Solution {
public:
    int longestSubstring(string s, int k) {
        
        int count[26]={0,};
        
        int maxUnique = 0;
        int len = s.length();
        for(int i=0; i<len; i++){
            count[s[i]-'a']++;
            if(count[s[i] - 'a'] == 1){
                maxUnique++;
            }
        }
        
        int result = 0;
        for(int cur=1; cur<=maxUnique; cur++){
            fill(count, count+26, 0);
            int start=0, end=0, unique=0,countK=0;
            
            while(end < len){
                if(unique <= cur){
                    if(count[s[end] - 'a'] == 0) unique++;
                    count[s[end] - 'a']++;
                    if(count[s[end] - 'a'] == k) countK++;
                    end++;
                }else {
                    if(count[s[start]-'a'] == k) countK--;
                    count[s[start]-'a']--;
                    if(count[s[start]-'a'] == 0) unique--;
                    start++;
                }
                
                if(unique == countK && unique == cur){
                    result = max(result, end-start);
                }
            }
        }
        return result;
    }
};