'2025/03/10'에 해당되는 글 2건

Leetcode Problem:

• Count of Substrings Containing Every Vowel and K Consonants II

Summary

• Count the number of substrings in a given word that contain every vowel at least once and exactly k consonants.

Approach

• Sliding Window Technique with Hash Map, using two helper functions to track vowel and consonant counts.

Complexity

• O(n^2), where n is the length of the word, due to nested loops in the sliding window approach.

Solution Code:

class Solution {
public:
    long countOfSubstrings(string word, int k) {
        return atLeastK(word, k) - atLeastK(word, k + 1);
    }

private:
    long atLeastK(string word, int k) {
        long numValidSubstrings = 0;
        int start = 0;
        int end = 0;
        // Keep track of counts of vowels and consonants.
        unordered_map vowelCount;
        int consonantCount = 0;

        // Start sliding window.
        while (end < word.length()) {
            // Insert new letter.
            char newLetter = word[end];

            // Update counts.
            if (isVowel(newLetter)) {
                vowelCount[newLetter]++;
            } else {
                consonantCount++;
            }

            // Shrink window while we have a valid substring.
            while (vowelCount.size() == 5 and consonantCount >= k) {
                numValidSubstrings += word.length() - end;
                char startLetter = word[start];
                if (isVowel(startLetter)) {
                    if (--vowelCount[startLetter] == 0) {
                        vowelCount.erase(startLetter);
                    }
                } else {
                    consonantCount--;
                }
                start++;
            }

            end++;
        }

        return numValidSubstrings;
    }

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

Leetcode Problem:

• Alternating Groups II

Summary

• Find the number of alternating groups in a circle of red and blue tiles

Approach

• This solution uses a circular approach to find the alternating groups
• It first extends the colors array to make it circular, then it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups and increments the counter if a group is found.

Complexity

• O(N) where N is the number of tiles in the circle

Explanation

• The solution works by first extending the colors array to make it circular
• This is done by adding the first element to the end of the array
• Then, it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups by comparing the current color with the previous color
• If the colors are alternating, it increments the counter
• Finally, it returns the counter as the number of alternating groups

Solution Code:

class Solution {
public:
    int numberOfAlternatingGroups(vector& colors, int k) {
        int N = colors.size();
        for(int i = 0 ; i < N; i++){
            colors.push_back(colors[i]);
        }
        int cnt = 1;
        int cur = colors[0] ^ 1;
        int ans = 0;
        for(int i = 1; i < k; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            cur = colors[i] ^ 1;
        }
        if(cnt >= k){
            ans++;
        }
        for(int i = k; i < N + k - 1; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            if(cnt >= k){
                ans++;
            }
            cur = colors[i] ^ 1;
        }
        return ans;
    }
};