# Count Beautiful Substrings I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-beautiful-substrings-i)
Canonical: https://scaleengineer.com/dsa/problems/count-beautiful-substrings-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Hash Table, String
---
## Problem
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.

# Approaches
## Brute-Force Iteration
This approach involves checking every possible non-empty substring of the given string `s`. For each substring, we count the number of vowels and consonants and then check if it satisfies the two conditions for being beautiful.
**Time:** O(n²), where n is the length of the string `s`. The two nested loops iterate through all possible substrings, and the work inside the inner loop is constant time. · **Space:** O(1)
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** The time complexity is quadratic, which might be too slow for very large input strings (though it passes for the given constraints).
### Explanation
We can generate all substrings by using two nested loops. The outer loop fixes the starting index `i` of the substring, and the inner loop iterates from `i` to the end of the string, fixing the ending index `j`. 

For each substring `s[i..j]`, instead of recounting vowels and consonants from scratch, we can maintain running counts. As we extend the substring by one character (by incrementing `j`), we update the `vowels` and `consonants` counts in O(1) time. After each update, we check if the current substring is beautiful. 

This avoids a third loop for counting, reducing the complexity from O(n³) to O(n²).

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    public int beautifulSubstrings(String s, int k) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i < n; i++) {
            int vowels = 0;
            int consonants = 0;
            for (int j = i; j < n; j++) {
                if (isVowel(s.charAt(j))) {
                    vowels++;
                } else {
                    consonants++;
                }
                if (vowels == consonants && (long)vowels * consonants % k == 0) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a variable `count` to 0 to store the number of beautiful substrings.
- Iterate through the string `s` with an outer loop using index `i` from `0` to `n-1`, where `n` is the length of `s`. This index `i` will be the starting point of a substring.
- Inside the outer loop, initialize `vowels = 0` and `consonants = 0`.
- Start an inner loop with index `j` from `i` to `n-1`. This index `j` will be the ending point of the substring `s[i..j]`.
- In the inner loop, check the character `s.charAt(j)`. If it's a vowel, increment `vowels`; otherwise, increment `consonants`.
- After updating the counts, check if the two conditions for a beautiful substring are met:
  1. `vowels == consonants`
  2. `(vowels * consonants) % k == 0`
- If both conditions are true, increment the `count`.
- After the loops complete, return the total `count`.

## Prefix State and Hashing
A more efficient approach uses prefix sums and a hash map to count valid substrings in linear time. The two conditions for a beautiful substring `s[i..j]` can be transformed into conditions on prefix properties, allowing us to avoid the nested loop.
**Time:** O(n + sqrt(k)). Calculating `k_prime` takes roughly O(sqrt(k)) time. The main loop iterates through the string once, with O(1) work (hash map operations) inside. Thus, the total time is dominated by the linear scan and `k_prime` calculation. · **Space:** O(n) in the worst case for the hash map, where `n` is the string length. The number of distinct states `(diff, vowels_mod)` can be at most `n+1`.
**Pros:** Highly efficient with linear time complexity.; Scales well for larger inputs.
**Cons:** More complex to understand and implement due to the number theory involved in calculating `k_prime`.; Uses more space for the hash map.
### Explanation
A substring `s[i..j]` is beautiful if `v_ij == c_ij` and `(v_ij * v_ij) % k == 0`.

1.  **Condition `v_ij == c_ij`**: Let `diff(x)` be the number of vowels minus consonants in the prefix `s[0..x-1]`. The condition `v_ij == c_ij` for the substring `s[i..j]` is equivalent to `diff(j+1) == diff(i)`.

2.  **Condition `(v_ij * v_ij) % k == 0`**: This condition holds if and only if `v_ij` is a multiple of a specific number, which we'll call `k_prime`. `k_prime` is the smallest integer `L` such that `(L * L) % k == 0`. This means we need `v_ij % k_prime == 0`. Since `v_ij` is the number of vowels in `s[i..j]`, which is `v_p(j+1) - v_p(i)` (where `v_p(x)` is the prefix vowel count), this is equivalent to `v_p(j+1) % k_prime == v_p(i) % k_prime`.

Combining these, we need to find pairs of indices `(i, j+1)` such that `diff(i) == diff(j+1)` and `v_p(i) % k_prime == v_p(j+1) % k_prime`. We can iterate through the string, calculating the state `(diff, v_p % k_prime)` at each position. A hash map can store the counts of previously seen states. For each new position, we add the count of its corresponding state to our total, then update the map.

```java
class Solution {
    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    private int calculateKPrime(int k) {
        int k_prime = 1;
        for (int i = 2; i * i <= k; i++) {
            if (k % i == 0) {
                int count = 0;
                while (k % i == 0) {
                    count++;
                    k /= i;
                }
                int required_exp = (count + 1) / 2;
                for (int j = 0; j < required_exp; j++) {
                    k_prime *= i;
                }
            }
        }
        if (k > 1) { // Remaining k is a prime factor
            k_prime *= k;
        }
        return k_prime;
    }

    public int beautifulSubstrings(String s, int k) {
        int k_prime = calculateKPrime(k);
        int n = s.length();
        // Using a String as a key for the pair (diff, vowels_mod)
        java.util.Map<String, Integer> counts = new java.util.HashMap<>();
        counts.put("0:0", 1); // Initial state for empty prefix
        
        int result = 0;
        int diff = 0; // vowels - consonants
        int vowels = 0;
        
        for (int i = 0; i < n; i++) {
            if (isVowel(s.charAt(i))) {
                vowels++;
                diff++;
            } else {
                diff--;
            }
            
            int vowels_mod = vowels % k_prime;
            String key = diff + ":" + vowels_mod;
            
            result += counts.getOrDefault(key, 0);
            counts.put(key, counts.getOrDefault(key, 0) + 1);
        }
        
        return result;
    }
}
```
### Algorithm
1.  **Compute `k_prime`**: Find the smallest integer `k_prime` such that `(k_prime * k_prime)` is divisible by `k`. This is done by finding the prime factorization of `k`. For each prime factor `p` with exponent `a` in `k`'s factorization, `k_prime` must have `p` with an exponent of at least `ceil(a/2)`.
2.  **Initialize**: Create a hash map `counts` to store the frequency of states. A state is a pair `(diff, vowels_mod_k_prime)`. Also, initialize `result = 0`, `diff = 0` (vowels - consonants), and `vowels = 0`.
3.  **Set Initial State**: The state for an empty prefix (before index 0) is `(diff=0, vowels_mod=0)`. Put this state into the map with a count of 1. `counts.put("0:0", 1)`.
4.  **Iterate through String**: Loop through the string `s` from `i = 0` to `n-1`.
    a.  Update `vowels` and `diff` based on the character `s.charAt(i)`.
    b.  Calculate the current state key: `key = diff + ":" + (vowels % k_prime)`.
    c.  The number of beautiful substrings ending at index `i` is the number of times this `key` has been seen before. Add `counts.getOrDefault(key, 0)` to `result`.
    d.  Increment the count for the current `key` in the map.
5.  **Return Result**: After the loop, `result` holds the total count of beautiful substrings.

# Solutions
### Java

```java
class Solution {
public
  int beautifulSubstrings(String s, int k) {
    int n = s.length();
    int[] vs = new int[26];
    for (char c : "aeiou".toCharArray()) {
      vs[c - 'a'] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int vowels = 0;
      for (int j = i; j < n; ++j) {
        vowels += vs[s.charAt(j) - 'a'];
        int consonants = j - i + 1 - vowels;
        if (vowels == consonants && vowels * consonants % k == 0) {
          ++ans;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int beautifulSubstrings(string s, int k) {
    int n = s.size();
    int vs[26]{};
    string t = "aeiou";
    for (char c : t) {
      vs[c - 'a'] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int vowels = 0;
      for (int j = i; j < n; ++j) {
        vowels += vs[s[j] - 'a'];
        int consonants = j - i + 1 - vowels;
        if (vowels == consonants && vowels * consonants % k == 0) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int: n = len(s) vs = set("aeiou") ans = 0 for i in range(n): vowels = 0 for j in range(i, n): vowels += s[j] in vs consonants = j - i + 1 - vowels if vowels == consonants and vowels * consonants % k == 0: ans += 1 return ans

```