Problem Description

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.

Intuition

To solve the problem of finding beautiful substrings, a strategic approach involves leveraging prefix sums and a hash table. Here's the reasoning behind the solution:

1. Counting Vowels and Consonants:

   • By assigning a specific value to each character in the string, it's possible to distinguish between vowels and consonants.
   • Using a bitmask (like AEIOU_MASK), each character of s can be quickly checked if it's a vowel.

2. Prefix Sum Technique:

   • As you iterate through the string, compute a running sum that increases or decreases based on whether the current character is a vowel or consonant.
   • A key insight is that when the prefix sum of vowels and consonants at two different indices is the same, the substring between these two indices has equal numbers of vowels and consonants.

3. Hash Map Utility:

   • Use a hash map to keep track of the number of times a particular prefix sum (combined with the modulus of its index) occurs.
   • For each character, compute a key based on the prefix sum and its index modulus. Check how many times this key has occurred previously.
   • Each previous occurrence of the same key corresponds to a valid beautiful substring.

4. Perfect Square Optimization via pSqrt Function:

   • The solution exploits properties of perfect squares to limit the search space effectively. By tuning the prefix sums with certain properties, we ensure that our calculations stay efficient and the substrings checked maintain the required criteria.

By applying these principles, the solution efficiently identifies all beautiful substrings using computationally effective operations.

Learn more about Math and Prefix Sum patterns.

Solution Approach

The solution centers around the [Prefix Sum](/problems/subarray_sum) technique combined with a Hash Table to efficiently track and count the desired substrings.

Key Components

1. AEIOU Mask:

   • The AEIOU_MASK is a bitmask representing vowels. For each character in the string s, this mask helps determine if the character is a vowel or consonant.

2. Prefix Sum Calculation:

   • As we iterate over the string s, we calculate a running sum sum that increases by 2 for vowels and decreases by 1 for consonants.
   • The idea is to use even and odd values to balance the counts of vowels and consonants.

3. Hash Table (Map):

   • A Map is used to keep track of the number of occurrences of each (index % l, sum) pair, where l is derived using the pSqrt function.
   • This (index % l, sum) pair effectively represents unique conditions for beautiful strings in terms of position and vowel/consonant balance.

4. Counting Beautiful Substrings:

   • As each character in the string s is processed, generate a key derived from the current index and sum.
   • If this key exists in the Map, it indicates the presence of previous indices with the same sum, which are potential starting points for a beautiful substring.
   • Increment the count of beautiful substrings (ans) based on the current count of the key in the Map.

5. Perfect Square Reduction:

   • The function pSqrt(k * 4) provides a reduced length l for prefix balancing. This calculation leverages mathematical properties associated with perfect squares to keep the process efficient and limit unnecessary checks.

Code Overview

Here's a breakdown of the code workflow:

function beautifulSubstrings(s: string, k: number): number {
    const l = pSqrt(k * 4); // Calculate a reduced length for efficient modulo operations.
    const n = s.length;
    let sum = n; // Initialize the sum using the length of the string.
    let ans = 0; // Initialize answer count.
    const counter = new Map(); // Map for tracking (index % l, sum) occurrences.
    counter.set(((l - 1) << 17) | sum, 1); // Initialize the map with a starting key.
  
    for (let i = 0; i < n; i++) {
        const char = s[i];
        const bit = (AEIOU_MASK >> (char.charCodeAt(0) - 'a'.charCodeAt(0))) & 1; // Check if character is a vowel.
        sum += bit * 2 - 1; // Adjust sum based on whether the character is a vowel or consonant.
        const key = (i % l << 17) | sum; // Create a unique key for (index % l, sum).
      
        ans += counter.get(key) || 0; // Increment answer with count of existing key.
        counter.set(key, (counter.get(key) ?? 0) + 1); // Update map with incremented count for the key.
    }
  
    return ans; // Return the total count of beautiful substrings.
}
const AEIOU_MASK = 1065233; // Binary mask for vowels.

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; // Returns the square root of n, adjusted for perfect square factors.
}

This approach efficiently manages the substring checks using arithmetic properties and hash mapping, ensuring both speed and accuracy.

Example Walkthrough

Consider the string s = "abbaaa" and k = 2.

1. Initial Setup:

   • l is calculated using pSqrt(k * 4). For k = 2, it computes to pSqrt(8), which simplifies to 2. This means we use a modulus base of 2 for our indexing.
   • Initialize sum = n = 6 (size of s), ans = 0, and a Map to keep track of seen keys.

2. Processing Characters:

   • Character 0 (a):

     • a is a vowel, so bit = 1.
     • Update sum using sum += bit * 2 - 1 = 6 + 2 - 1 = 7.
     • Calculate key with key = (0 % 2 << 17) | 7 = 7.
     • Check the Map for key 7 and increment ans by counter[7] which is 0 initially.
     • Update the Map: counter[7] = 1.

   • Character 1 (b):

     • b is a consonant, so bit = 0.
     • Update sum using sum += bit * 2 - 1 = 7 - 1 = 6.
     • Calculate key with key = (1 % 2 << 17) | 6 = 131078.
     • Check the Map for key 131078 and increment ans by counter[131078] which is 0 initially.
     • Update the Map: counter[131078] = 1.

   • Character 2 (b):

     • b is a consonant, so bit = 0.
     • Update sum using sum += bit * 2 - 1 = 6 - 1 = 5.
     • Calculate key with key = (2 % 2 << 17) | 5 = 5.
     • Check the Map for key 5 and increment ans by counter[5] which is 0 initially.
     • Update the Map: counter[5] = 1.

   • Character 3 (a):

     • a is a vowel, so bit = 1.
     • Update sum using sum += bit * 2 - 1 = 5 + 2 - 1 = 6.
     • Calculate key with key = (3 % 2 << 17) | 6 = 131078.
     • Check the Map for key 131078 and increment ans by counter[131078] which is 1.
     • Update ans: ans = 1.
     • Update the Map: counter[131078] = 2.

   • Character 4 (a):

     • a is a vowel, so bit = 1.
     • Update sum using sum += bit * 2 - 1 = 6 + 2 - 1 = 7.
     • Calculate key with key = (4 % 2 << 17) | 7 = 7.
     • Check the Map for key 7 and increment ans by counter[7] which is 1.
     • Update ans: ans = 2.
     • Update the Map: counter[7] = 2.

   • Character 5 (a):

     • a is a vowel, so bit = 1.
     • Update sum using sum += bit * 2 - 1 = 7 + 2 - 1 = 8.
     • Calculate key with key = (5 % 2 << 17) | 8 = 131080.
     • Check the Map for key 131080 and increment ans by counter[131080] which is 0.
     • Update the Map: counter[131080] = 1.

3. Return the Result:

   • The total number of beautiful substrings found is ans = 2.

In this walk-through, we derived 2 beautiful substrings from the existing setup. This explanation demonstrates how the algorithm efficiently scopes through each character, updates its internal state, and counts substrings that meet the specified criteria using prefix sums and hash mapping.

Solution Implementation

Time and Space Complexity

The time complexity of the beautifulSubstrings function is O(n), where n is the length of the input string s. This is because the function iterates over the string with a single loop running n times. Each operation inside the loop, including accessing and updating the Map, takes constant time on average.

The pSqrt function runs in O(sqrt(k)) time complexity, which is the time taken to find the perfect square root decomposition using trial division up to the square root of k.

Overall, the time complexity of the combined code is O(n + sqrt(k)).

The space complexity is O(l + n), where l is the result of pSqrt(k * 4). This includes the space used by the counter Map which can store up to O(n) entries, each representing a unique state combination of (i % l << 17) | sum.

Learn more about how to find time and space complexity quickly.