2947. Count Beautiful Substrings I LeetCode Solution

In this guide, you will get 2947. Count Beautiful Substrings I LeetCode Solution with the best time and space complexity. The solution to Count Beautiful Substrings I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Beautiful Substrings I solution in C++
Count Beautiful Substrings I solution in Java
Count Beautiful Substrings I solution in Python
Additional Resources

2947. Count Beautiful Substrings I LeetCode Solution image

Problem Statement of Count Beautiful Substrings I

You are given a string s and a positive integer k.
Let vowels and consonants be the number of vowels and consonants in a string.
A string is beautiful if:

vowels == consonants.
(vowels * consonants) % k == 0, in other terms the multiplication of vowels and consonants is divisible by k.

Return the number of non-empty beautiful substrings in the given string s.
A substring is a contiguous sequence of characters in a string.
Vowel letters in English are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’.
Consonant letters in English are every letter except vowels.

Example 1:

Input: s = “baeyh”, k = 2
Output: 2
Explanation: There are 2 beautiful substrings in the given string.
– Substring “baeyh”, vowels = 2 ([“a”,e”]), consonants = 2 ([“y”,”h”]).
You can see that string “aeyh” is beautiful as vowels == consonants and vowels * consonants % k == 0.
– Substring “baeyh”, vowels = 2 ([“a”,e”]), consonants = 2 ([“b”,”y”]).
You can see that string “baey” is beautiful as vowels == consonants and vowels * consonants % k == 0.
It can be shown that there are only 2 beautiful substrings in the given string.

Example 2:

Input: s = “abba”, k = 1
Output: 3
Explanation: There are 3 beautiful substrings in the given string.
– Substring “abba”, vowels = 1 ([“a”]), consonants = 1 ([“b”]).
– Substring “abba”, vowels = 1 ([“a”]), consonants = 1 ([“b”]).
– Substring “abba”, vowels = 2 ([“a”,”a”]), consonants = 2 ([“b”,”b”]).
It can be shown that there are only 3 beautiful substrings in the given string.

Example 3:

Input: s = “bcdf”, k = 1
Output: 0
Explanation: There are no beautiful substrings in the given string.

Constraints:

1 <= s.length <= 1000
1 <= k <= 1000
s consists of only English lowercase letters.

Complexity Analysis

Time Complexity: O(|\texttt{s}| + k)
Space Complexity: O(|\texttt{s}| + k)

2947. Count Beautiful Substrings I LeetCode Solution in C++

class Solution {
 public:
  int beautifulSubstrings(string s, int k) {
    const int root = getRoot(k);
    int ans = 0;
    int vowels = 0;
    int vowelsMinusConsonants = 0;
    // {(vowels, vowelsMinusConsonants): count}
    unordered_map<pair<int, int>, int, PairHash> prefixCount{{{0, 0}, 1}};

    for (const char c : s) {
      if (isVowel(c)) {
        vowels = (vowels + 1) % root;
        ++vowelsMinusConsonants;
      } else {
        --vowelsMinusConsonants;
      }
      const pair<int, int> prefix{vowels, vowelsMinusConsonants};
      ans += prefixCount[prefix]++;
    }

    return ans;
  }

 private:
  bool isVowel(char c) {
    static constexpr string_view kVowels = "aeiouAEIOU";
    return kVowels.find(c) != string_view::npos;
  }

  int getRoot(int k) {
    for (int i = 1; i <= k; ++i)
      if (i * i % k == 0)
        return i;
    throw;
  }

  struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };
};
/* code provided by PROGIEZ */

2947. Count Beautiful Substrings I LeetCode Solution in Java

class Solution {
  public int beautifulSubstrings(String s, int k) {
    final int root = getRoot(k);
    int ans = 0;
    int vowels = 0;
    int vowelsMinusConsonants = 0;
    // {(vowels, vowelsMinusConsonants): count}
    Map<Pair<Integer, Integer>, Integer> prefixCount = new HashMap<>();
    prefixCount.put(new Pair<>(0, 0), 1);

    for (final char c : s.toCharArray()) {
      if (isVowel(c)) {
        vowels = (vowels + 1) % root;
        ++vowelsMinusConsonants;
      } else {
        --vowelsMinusConsonants;
      }
      Pair<Integer, Integer> prefix = new Pair<>(vowels, vowelsMinusConsonants);
      ans += prefixCount.getOrDefault(prefix, 0);
      prefixCount.merge(prefix, 1, Integer::sum);
    }

    return ans;
  }

  private boolean isVowel(char c) {
    return "aeiou".indexOf(c) != -1;
  }

  private int getRoot(int k) {
    for (int i = 1; i <= k; ++i)
      if (i * i % k == 0)
        return i;
    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

2947. Count Beautiful Substrings I LeetCode Solution in Python

class Solution:
  def beautifulSubstrings(self, s: str, k: int) -> int:
    kVowels = 'aeiou'
    root = self._getRoot(k)
    ans = 0
    vowels = 0
    vowelsMinusConsonants = 0
    # {(vowels, vowelsMinusConsonants): count}
    prefixCount = collections.Counter({(0, 0): 1})

    for c in s:
      if c in kVowels:
        vowelsMinusConsonants += 1
        vowels = (vowels + 1) % root
      else:
        vowelsMinusConsonants -= 1
      ans += prefixCount[(vowels, vowelsMinusConsonants)]
      prefixCount[(vowels, vowelsMinusConsonants)] += 1

    return ans

  def _getRoot(self, k: int) -> int:
    for i in range(1, k + 1):
      if i * i % k == 0:
        return i
 # code by PROGIEZ