LeetCode 3306 (Daily Challenge - java)

https://leetcode.com/problems/count-of-substrings-containing-every-vowel-and-k-consonants-ii/?envType=daily-question&envId=2025-03-18

Description

You are given a string word and a non-negative integer k.

Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

---

문제 설명을 해보면
word문자열, 양수 k가 주어진다.
모음 a,e,i,o,u가 적어도 한개 이상씩 포함되고, 자음이 k개만큼 정확히 일치하는 word의 subString개수를 구하여라.

example

Input: word = "ieaouqqieaouqq", k = 1

Output: 3

Explanation:

The substrings with every vowel and one consonant are:

word[0..5], which is "ieaouq". -> 모음 5개 자음 1개
word[6..11], which is "qieaou". -> 모음 5개 자음 1개
word[7..12], which is "ieaouq". -> 모음 5개 자음 1개

문제 접근 방식

1. 모음이 나오는 가장 마지막 인덱스를 저장한다.

input : a e i o q u q, k = 1
a e i o q u a q
4 4 4 4 4 7 7 7

이런식으로 인덱스가 저장된다면
조건식이 kCount == k AND 모든 모음 > 0 조건에서 처음으로 r은 u에서 멈추게 될텐데 r - l 을 하게되면 그 뒤에 aeioqua까지 못구하게 된다. 따라서 인덱스를 저장하게 하면 index[r + 1] - r 하면 가능한 길이가 나오게 된다.

최종 코드

class Solution {
    public long countOfSubstrings(String word, int k) {
        
        int[] frontCon = new int[200001];
        int[] vowelArr = new int[5];
        int len = word.length();
        frontCon[len] = len;

        for(int i = len - 1; i >= 0; i--){
            if(vowel(word.charAt(i))){
                frontCon[i] = frontCon[i + 1];
            }else{
                frontCon[i] = i;
            }
        }

        int r = -1;
        int kCnt = 0;
        long result = 0;
        for(int l=0; l < len; l++){

            while((kCnt < k || !isVowel(vowelArr)) && r + 1 < len){
                r++;
                char c = word.charAt(r);
                if(vowel(c)){
                    vowelAddArray(c,vowelArr);
                }else{
                    kCnt++;
                }
            }

            if(isVowel(vowelArr) && kCnt == k){
                result += frontCon[r + 1] - r;
            }

            char c = word.charAt(l);
            if(vowel(c)){
                vowelRemoveArray(c,vowelArr);
            }else{
                kCnt--;
            }
        }
        return result;
    }

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

    private void vowelAddArray(char c, int[] vowelArr){
        if(c == 'a') vowelArr[0]++;
        else if(c == 'e') vowelArr[1]++;
        else if(c == 'i') vowelArr[2]++;
        else if(c == 'o') vowelArr[3]++;
        else if(c == 'u') vowelArr[4]++;
    }

    private void vowelRemoveArray(char c, int[] vowelArr){
        if(c == 'a') vowelArr[0]--;
        else if(c == 'e') vowelArr[1]--;
        else if(c == 'i') vowelArr[2]--;
        else if(c == 'o') vowelArr[3]--;
        else if(c == 'u') vowelArr[4]--;
    }

    private boolean isVowel(int[] vowelArr){
        for(int value : vowelArr){
            if(value <= 0) return false;
        }
        return true;
    }
}