395. Longest Substring with At Least K Repeating Characters

문제

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

풀이 사고

• k보다 적은 카운트의 경우 k위치를 기준으로 자른다음 재귀로 문제 접근
• ex ) ababcaaad k=2
  • 전체의 카운트
    • a = 5, b=2, c=1; d=1 즉 k보다 작은게 존재하면 작은 캐릭터 기준으로 자른다
    • c 와 d 를 콤마(,)로 치환
    • abab,aaa,
    • , 를 기준으로 split한후 다시 자른 String으로 반복로직 구현

Runtime: 3 ms, faster than 77.01% of Java online submissions for Longest Substring with At Least K Repeating Characters.

class Solution {
    int max;

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

        if(k>s.length()){return 0;}
        findMax(s, k);
        return max;
    }

    public void findMax(String s, int k){
        int arr[] = new int['z' - 'a' +1];

        // setting
        for(int i=0; i<s.length(); i++){
            int index = s.charAt(i) -'a';
            arr[index]++;
        }

        // 전부다 k보다 더 큰 수가 나오는 경우는 max값을 갱신
        if(allEqualOrBigger(arr, k)){
           max = Math.max(max, s.length());
        }else{
            char[] str= new char[s.length()];
            for(int i=0; i<s.length(); i++){
                int index = s.charAt(i) -'a';

                if(arr[index] == 0 ){
                    continue;
                }else if(arr[index] >=k){ //
                    str[i] = s.charAt(i);
                }else{
                    str[i] = ',';
                }
            }
            String[] subs = new String(str).split(",");
            for(int i=0; i<subs.length; i++){
                if(subs[i].length() <= max){
                    continue;
                }
                findMax(subs[i], k);
            }
        }
    }

    public boolean allEqualOrBigger(int arr[], int k){
        for(int i=0; i< arr.length; i++){
            if(arr[i] >0 && arr[i]<k){
                return false;
            }
        }
        return true;
    }
}