1456. Maximum Number of Vowels in a Substring of Given Length

문제

https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/

풀이

class Solution {
    public int maxVowels(String s, int k) {
        char[] arr = s.toCharArray();
        int answer = 0;
        int count = 0;
        int lt = 0;
        // 처음 k 길이 만큼의 subarray에서 모음 개수구하기
         for(int rt = 0; rt < k; rt++) {
            if(isVowel(arr[rt])) {
                count++;
            }
        }

        answer = count;

        for(int rt = k; rt < s.length(); rt++) {
             if(isVowel(arr[rt])) {
                count++;
            }
            if(isVowel(arr[lt])) {
                count--;
                lt++;
            } else {
                lt++;
            }
            answer = Math.max(count, answer);
        }

        return answer; 
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

• k 길이만큼 고정된 subarray를 전부 탐색하면서, 모음의 개수가 가장 많은 subarray의 모음 수를 구하는 문제
  • 고정 길이 sliding window 사용!
• 첫 sliding window에서 모음의 개수를 먼저 세어주고,
  rt = k 부터 시작해서 모음이 있는지 확인 후, lt를 한칸씩 오른쪽으로 밀어주면 된다.
  lt가 모음인 경우, count를 하나 빼서 밀어주고, 아닌 경우엔 그냥 밀어주기!
• 그 후, 다시 answer과 count 중 최대값이 뭔지 비교

• lt와 rt가 각각 전체 배열을 한번씩 도니까 O(N) + O(N)
• 시간 복잡도 O(N)의 풀이