Count Unique Vowel Strings

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Count strings of length n containing all 5 vowels at least once. Inclusion-exclusion on vowel alphabet.

Algorithm

1Total strings with exactly all 5 vowels = inclusion-exclusion: subtract missing one vowel, add back two missing, etc.

Common Pitfalls

•Stars and bars with inclusion-exclusion. Or DP: dp[i][mask] = strings of length i containing vowels in mask.

Count Unique Vowel Strings.java

Java

// Approach: Count vowels in each string. Use combinatorics or counting argument to find unique arrangements.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int vowelCount(String s) {
        int a = 0;
        HashMap<Character, Integer> hm = new HashMap<>();
        for (char ch : s.toCharArray()) {
            if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
                hm.put(ch, hm.getOrDefault(ch, 0) + 1);
        }

        if (hm.size() == 0)
            return a;

        a = fact(hm.size());
        for (char ch : hm.keySet())
            a = a * hm.get(ch);

        return a;
    }

    int fact(int n) {
        if (n == 0 || n == 1)
            return 1;
        else
            return n * fact(n - 1);
    }

}

Was this solution helpful?