[LeetCode] 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/

Maximum Number of Vowels in a Substring of Given Length - LeetCode

문제 유형 : 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

 

입력되는 문자열 s와 정수 k가 있다. s문자열 안에서 k의 길이를 가진 부속 문자열이 가질 수 있는 최대의 모음개수를 반환하여라.

 

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

 

풀이

슬라이딩 윈도우로 최적해를 구해주면 된다.

슬라이딩 윈도우의 개념을 모른 채로 풀어서 원래 아는 형태로 나오지는 않았지만, 로직은 비슷하게 풀었다.

다음 substring으로 넘어갈 때에는 substring 큐에서 pop하고 뒤에 새로운 걸 push_back하는데, 이 과정에서 모음인 경우 substring의 모음개수를 조정한다.

 

코드(C++)

class Solution {
public:
    int maxVowels(string s, int k) {
        int max;
        int current = 0;
        deque<char> substring;
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};

        for(int i = 0; i < k; i++){
            substring.push_back(s[i]);
            if(vowels.count(s[i])){
                current++;
            }
        }
        max = current;

        for(int i = k; i < s.length(); i++){
            if(vowels.count(substring.front())){
                current--;
            }
            substring.pop_front();
            substring.push_back(s[i]);
            if(vowels.count(s[i])){
                current++;
            }
            if(current > max){
                max = current;
            }
        }
        return max;
    }
};