# Count Beautiful Substrings II
**Difficulty:** HARD
[External](https://leetcode.com/problems/count-beautiful-substrings-ii)
Canonical: https://scaleengineer.com/dsa/problems/count-beautiful-substrings-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [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 <= 5 * 104`
* `1 <= k <= 1000`
* `s` consists of only English lowercase letters.

# Approaches
## Brute Force with Optimization
This approach involves checking every possible substring of the given string `s`. For each substring, we count the vowels and consonants and verify if it meets the two conditions for being 'beautiful'. To avoid a TLE (Time Limit Exceeded) error from a naive `O(N^3)` implementation, we optimize the counting process.
**Time:** O(N^2), where N is the length of the string `s`. The two nested loops iterate through all `O(N^2)` substrings, and the check for each is O(1). · **Space:** O(1), as we only use a few variables to store counts, regardless of the input size.
**Pros:** Simple to understand and implement.; Low memory usage.
**Cons:** Inefficient for large inputs, leading to Time Limit Exceeded (TLE).
### Explanation
We can iterate through all possible starting positions `i` of a substring. For each `i`, we start another loop for the ending position `j` from `i` to the end of the string. As we extend the substring by one character at `j`, we maintain a running count of vowels and consonants. This allows us to check the conditions for the substring `s[i...j]` in `O(1)` time within the inner loop.

The two conditions for a beautiful substring are:
1. `vowels == consonants`
2. `(vowels * consonants) % k == 0`

If both are true for the current substring, we increment our result counter.

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

    public long beautifulSubstrings(String s, int k) {
        long count = 0;
        int n = s.length();
        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 > 0 && vowels == consonants) {
                    if ((long)vowels * vowels % k == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
This approach is straightforward but its quadratic time complexity makes it too slow for the given constraints.
### Algorithm
- Initialize a counter `ans` to 0.
- Iterate through the string with a starting index `i` from 0 to `n-1`.
- For each `i`, initialize `vowels = 0` and `consonants = 0`.
- Start a nested loop for the ending index `j` from `i` to `n-1`.
  - Update `vowels` and `consonants` based on the character `s[j]`.
  - Check if `vowels > 0` and `vowels == consonants`.
  - If true, check if `(vowels * vowels) % k == 0`.
  - If both conditions are met, increment `ans`.
- Return `ans`.

## Prefix Difference with Hashing and Modular Arithmetic
This optimal solution leverages number theory and prefix sums (differences) to count beautiful substrings in linear time. By transforming the two conditions into properties of prefix states, we can use a hash map to efficiently find matching substrings without iterating through all of them.
**Time:** O(N + sqrt(K)), where N is the string length. Calculating the `period` takes `O(sqrt(K))`. The main loop is `O(N)` with `O(1)` average time for hash map operations. · **Space:** O(N). The hash map can store up to N+1 distinct states in the worst case.
**Pros:** Highly efficient with linear time complexity.; Scales well for large inputs.
**Cons:** The logic is complex and relies on number theory, making it less intuitive.; Requires careful implementation of state representation and modular arithmetic.
### Explanation
The problem's conditions can be rephrased to enable a more efficient counting method. Let's analyze a substring `s[i...j]`.

1.  **`vowels == consonants`**: We can model this by assigning `+1` to vowels and `-1` to consonants. A substring satisfies this condition if the sum of these values over its characters is 0. Using a prefix difference array `diff`, where `diff[x]` is the net sum for the prefix `s[0...x]`, this condition becomes `diff[j] == diff[i-1]`.

2.  **`(vowels * consonants) % k == 0`**: Since `vowels == consonants`, the substring length `L = j - i + 1` must be even, with `vowels = L / 2`. The condition becomes `(L/2)^2 % k == 0`, which simplifies to `L^2 % (4*k) == 0`. This number theory condition holds if and only if `L` is a multiple of a specific number, which we'll call `period`. This `period` is derived from the prime factorization of `4*k`. The condition `L % period == 0` is equivalent to `(j - (i-1)) % period == 0`, which means `j % period == (i-1) % period`.

Combining these, we need to find pairs of indices `(p, j)` (where `p = i-1`) that satisfy `diff[j] == diff[p]` and `j % period == p % period`. We can iterate through the string, tracking the state `(diff, index % period)`. A hash map stores the frequencies of these states, allowing us to find the number of valid starting points for each ending point `j` in `O(1)` time.

```java
import java.util.HashMap;
import java.util.Map;

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

    private int calculatePeriod(int k) {
        long num = 4L * k;
        int period = 1;
        for (long i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                int count = 0;
                while (num % i == 0) {
                    count++;
                    num /= i;
                }
                for (int j = 0; j < (count + 1) / 2; j++) {
                    period *= i;
                }
            }
        }
        if (num > 1) {
            period *= num;
        }
        return period;
    }

    public long beautifulSubstrings(String s, int k) {
        int period = calculatePeriod(k);
        int n = s.length();
        Map<String, Integer> counts = new HashMap<>();
        
        int initialRem = (-1 % period + period) % period;
        counts.put("0:" + initialRem, 1);

        long ans = 0;
        int diff = 0;

        for (int j = 0; j < n; j++) {
            if (isVowel(s.charAt(j))) {
                diff++;
            } else {
                diff--;
            }

            int rem = j % period;
            String key = diff + ":" + rem;
            
            int prevCount = counts.getOrDefault(key, 0);
            ans += prevCount;
            
            counts.put(key, prevCount + 1);
        }

        return ans;
    }
}
```
### Algorithm
- Calculate a `period` based on `4*k`. This is done by finding the prime factorization of `4*k` and constructing a new number where each prime `p` with exponent `a` is replaced by `p` with exponent `ceil(a/2)`.
- Initialize `ans = 0`, `diff = 0`.
- Initialize a hash map `counts` to store frequencies of `(diff, index % period)` states.
- Put the initial state for an index `p = -1` into the map: `diff = 0`, `rem = (-1 % period + period) % period`. The count for state `(0, rem)` is 1.
- Iterate through the string with index `j` from 0 to `n-1`:
  - Update `diff` based on `s[j]` (+1 for vowel, -1 for consonant).
  - Calculate `rem = j % period`.
  - Form the state key from `(diff, rem)`.
  - Get the count of this state from the `counts` map and add it to `ans`.
  - Increment the count for the current state in the map.
- Return `ans`.