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

문제

주어진 문자열에서 모든 k길이의 substring 중에서 모음이 가장많은 substring의 모음 갯수는?

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.
Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.
Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

아이디어

• O(n)/O(1) k 사이즈 만큼의 윈도우를 한칸씩 우측으로 이동. 윈도우의 맨 오른쪽에 들어올 다음 문자와 윈도우의 맨 왼쪽에서 제거될 문자에 모음이 있는지 확인하고 갯수 변경.

풀이

class Solution {
public:
    bool is_vowel(char c) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
            return true;
        return false;
    }
    int maxVowels(string s, int k) {
        int vcnt = 0;
        for (int i = 0; i < k; i++) {
            if (is_vowel(s[i]))
                vcnt++;
        }
        int max_vcnt = vcnt;
        int past = 0;
        for (int i = k; i < s.length(); i++) {
            if (is_vowel(s[i]))
                vcnt++;
            if (is_vowel(s[past++]))
                vcnt--;
            max_vcnt = max(vcnt, max_vcnt);
        }
        return max_vcnt;
    }
};