#2949

Hard

LeetCode Problem Workspace

Count Beautiful Substrings II

Count Beautiful Substrings II focuses on finding beautiful substrings with hash tables and number theory techniques.

hash table math string number theory prefix sum

Problem Statement

You are given a string s and a positive integer k. A string is considered beautiful if the number of vowels and consonants are equal, and the product of the number of vowels and consonants modulo k equals 0.

Your task is to find how many beautiful substrings exist within the given string. A substring is defined as a contiguous sequence of characters. You need to consider all substrings of s and determine how many of them satisfy the given conditions.

Examples

Example 1

Input: s = "baeyh", k = 2

Output: 2

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

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

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.

Solution Approach

Mathematical Insight

To solve this problem, first realize that the condition vowels * consonants % k == 0 must hold. This requires finding numbers x where x^2 % k == 0, as these pairs are crucial for checking the product condition.

Prefix Sum Optimization

By using a prefix sum approach, you can track the number of vowels and consonants at each point in the string. This allows you to efficiently compute the number of vowels and consonants in any substring in constant time.

Hash Table Usage

A hash table can be used to store the frequency of encountered vowel-consonant pairs modulo k. This helps in quickly determining how many valid substrings can be formed by adding each new character to the substring.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the efficiency of the hash table updates and the prefix sum calculations. Using these optimizations, the solution can process the input in linear time, O(n), where n is the length of the string. Space complexity is O(k), due to the storage of possible modulo values in the hash table.

What Interviewers Usually Probe

Look for clear understanding of prefix sums and hash table usage.
Candidates should identify mathematical properties of the problem, such as the x^2 % k == 0 condition.
The candidate should demonstrate an ability to optimize the brute force solution using efficient data structures.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for the modulo condition in the product of vowels and consonants.
Not optimizing the solution with prefix sums or hash tables, resulting in excessive time complexity.
Confusing the conditions for a valid substring by incorrectly matching vowel and consonant counts.

Follow-up variants

Change the conditions to require a different relationship between vowels and consonants, such as vowels being greater than consonants.
Increase the string length and adjust k to test how the solution handles larger inputs.
Modify the problem to work with a different alphabet or consider case sensitivity.

FAQ

What is the main strategy to solve Count Beautiful Substrings II?

The main strategy involves using hash tables for efficient tracking of vowel-consonant pairs and leveraging mathematical insights about the product modulo k condition.

How does the prefix sum optimization work in this problem?

The prefix sum optimization allows you to compute the number of vowels and consonants in any substring in constant time, improving efficiency.

What does `x^2 % k == 0` mean in the context of the problem?

It means that the product of vowels and consonants in the substring must be divisible by k. This is a key mathematical insight to optimize the solution.

Can the solution handle very large strings efficiently?

Yes, by using hash tables and prefix sums, the solution runs in linear time, O(n), making it efficient enough for large inputs.

What is the space complexity of the solution?

The space complexity is O(k), as the hash table stores the modulo values for the product of vowels and consonants.

terminal

Solution

Solution 1: Prefix Sum + Hash Table

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

function beautifulSubstrings(s: string, k: number): number {
    const l = pSqrt(k * 4);
    const n = s.length;
    let sum = n;
    let ans = 0;
    const counter = new Map();
    counter.set(((l - 1) << 17) | sum, 1);
    for (let i = 0; i < n; i++) {
        const char = s[i];
        const bit = (AEIOU_MASK >> (char.charCodeAt(0) - 'a'.charCodeAt(0))) & 1;
        sum += bit * 2 - 1; // 1 -> 1    0 -> -1
        const key = ((i % l) << 17) | sum;
        ans += counter.get(key) || 0; // ans += cnt[(i%k,sum)]++
        counter.set(key, (counter.get(key) ?? 0) + 1);
    }
    return ans;
}
const AEIOU_MASK = 1065233;

function pSqrt(n: number) {
    let res = 1;
    for (let i = 2; i * i <= n; i++) {
        let i2 = i * i;
        while (n % i2 == 0) {
            res *= i;
            n /= i2;
        }
        if (n % i == 0) {
            res *= i;
            n /= i;
        }
    }
    if (n > 1) {
        res *= n;
    }
    return res;
}

Continue Practicing

#2947 count beautiful substrings i #3312 sorted gcd pair queries #3556 sum of largest prime substrings