Problem Description

You need to find how many substrings in a given string s are "beautiful" according to specific criteria.

A substring is considered beautiful if it meets both of these conditions:

1. The number of vowels equals the number of consonants in the substring
2. The product of the number of vowels and consonants is divisible by a given positive integer k (i.e., (vowels * consonants) % k == 0)

The vowels are defined as the letters 'a', 'e', 'i', 'o', and 'u'. All other letters are considered consonants.

For example, if we have a substring with 2 vowels and 2 consonants:

• Condition 1 is satisfied (2 == 2)
• For condition 2, we check if (2 * 2) % k == 0, which depends on the value of k

The solution uses a brute force approach with two nested loops:

• The outer loop iterates through each starting position i in the string
• The inner loop extends from position i to create all possible substrings starting at i
• For each substring from index i to j, it counts the vowels
• The consonants count is calculated as (j - i + 1) - vowels (total length minus vowels)
• If both conditions are met, the answer counter is incremented

The algorithm checks all possible non-empty substrings and returns the total count of beautiful substrings found.

Intuition

The key insight is that we need to examine every possible substring to check if it's beautiful, since there's no clear pattern that would allow us to skip certain substrings or use a more optimized approach directly.

When we think about counting substrings with specific properties, a natural starting point is to generate all possible substrings. For a string of length n, there are n * (n + 1) / 2 possible substrings, which suggests an O(n²) approach might be reasonable.

The observation that makes the brute force approach efficient enough is that we can incrementally build our vowel count as we extend a substring. Instead of recounting vowels for each new substring from scratch, we:

1. Fix a starting position i
2. Extend the substring one character at a time by incrementing j
3. Update our vowel count by just checking if the new character s[j] is a vowel

Since we know the total length of the current substring is j - i + 1, we can derive the consonant count without additional iteration: consonants = (j - i + 1) - vowels.

The two conditions for a beautiful substring are straightforward to check:

• Equal vowels and consonants: vowels == consonants
• Divisibility: (vowels * consonants) % k == 0

This incremental approach avoids redundant counting - we build upon previous calculations rather than starting fresh for each substring. While we're still checking all O(n²) substrings, we're doing constant-time work for each one, making the overall complexity O(n²) which is acceptable for reasonable string lengths.

Learn more about Math and Prefix Sum patterns.

Solution Approach

The solution implements a nested loop approach to examine all possible substrings:

1. Initialize variables:

   • n = len(s) stores the string length
   • vs = set("aeiou") creates a set for O(1) vowel lookup
   • ans = 0 initializes the counter for beautiful substrings

2. Outer loop - Starting positions:

   for i in range(n):

   This loop iterates through each possible starting position of a substring.

3. Inner loop - Extending substrings:

   vowels = 0
   for j in range(i, n):

   For each starting position i, we extend the substring to position j. We reset the vowel count to 0 before examining substrings starting at position i.

4. Incremental vowel counting:

   vowels += s[j] in vs

   This uses Python's boolean-to-integer conversion. If s[j] is a vowel (exists in set vs), the expression evaluates to True which adds 1 to vowels. Otherwise, it adds 0.

5. Calculate consonants:

   consonants = j - i + 1 - vowels

   The total substring length is j - i + 1. Subtracting the vowel count gives us the consonant count.

6. Check beautiful conditions:

   if vowels == consonants and vowels * consonants % k == 0:
       ans += 1

   Both conditions must be satisfied:

   • Equal counts: vowels == consonants
   • Divisibility: (vowels * consonants) % k == 0

The algorithm systematically checks every substring from s[i:j+1] where i ranges from 0 to n-1 and j ranges from i to n-1. The use of a set for vowel checking ensures O(1) lookup time, and the incremental counting avoids redundant work within each inner loop iteration.

Example Walkthrough

Let's walk through the solution with s = "baeyh" and k = 2.

Initial Setup:

• n = 5 (length of string)
• vs = {'a', 'e', 'i', 'o', 'u'} (vowel set)
• ans = 0 (counter for beautiful substrings)

Iteration Process:

i = 0 (starting at 'b'):

• j = 0: substring = "b"
  • vowels = 0 ('b' is not a vowel)
  • consonants = 1 - 0 = 1
  • Check: 0 ≠ 1, not beautiful
• j = 1: substring = "ba"
  • vowels = 0 + 1 = 1 ('a' is a vowel)
  • consonants = 2 - 1 = 1
  • Check: 1 == 1 ✓ and 1 * 1 % 2 = 1 % 2 = 1 ✗, not beautiful
• j = 2: substring = "bae"
  • vowels = 1 + 1 = 2 ('e' is a vowel)
  • consonants = 3 - 2 = 1
  • Check: 2 ≠ 1, not beautiful
• j = 3: substring = "baey"
  • vowels = 2 + 0 = 2 ('y' is not a vowel)
  • consonants = 4 - 2 = 2
  • Check: 2 == 2 ✓ and 2 * 2 % 2 = 4 % 2 = 0 ✓, beautiful! ans = 1
• j = 4: substring = "baeyh"
  • vowels = 2 + 0 = 2 ('h' is not a vowel)
  • consonants = 5 - 2 = 3
  • Check: 2 ≠ 3, not beautiful

i = 1 (starting at 'a'):

• j = 1: substring = "a"
  • vowels = 1, consonants = 0
  • Check: 1 ≠ 0, not beautiful
• j = 2: substring = "ae"
  • vowels = 2, consonants = 0
  • Check: 2 ≠ 0, not beautiful
• j = 3: substring = "aey"
  • vowels = 2, consonants = 1
  • Check: 2 ≠ 1, not beautiful
• j = 4: substring = "aeyh"
  • vowels = 2, consonants = 2
  • Check: 2 == 2 ✓ and 2 * 2 % 2 = 0 ✓, beautiful! ans = 2

i = 2 (starting at 'e'):

• j = 2: substring = "e"
  • vowels = 1, consonants = 0
  • Check: 1 ≠ 0, not beautiful
• j = 3: substring = "ey"
  • vowels = 1, consonants = 1
  • Check: 1 == 1 ✓ and 1 * 1 % 2 = 1 ✗, not beautiful
• j = 4: substring = "eyh"
  • vowels = 1, consonants = 2
  • Check: 1 ≠ 2, not beautiful

i = 3 (starting at 'y'):

• j = 3: substring = "y"
  • vowels = 0, consonants = 1
  • Check: 0 ≠ 1, not beautiful
• j = 4: substring = "yh"
  • vowels = 0, consonants = 2
  • Check: 0 ≠ 2, not beautiful

i = 4 (starting at 'h'):

• j = 4: substring = "h"
  • vowels = 0, consonants = 1
  • Check: 0 ≠ 1, not beautiful

Final Result: ans = 2

The beautiful substrings found are "baey" and "aeyh", both having 2 vowels and 2 consonants, with their product (4) divisible by k=2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses two nested loops:

• The outer loop runs from i = 0 to i = n-1, iterating n times
• The inner loop runs from j = i to j = n-1, iterating up to n-i times for each i
• The total number of iterations is n + (n-1) + (n-2) + ... + 1 = n(n+1)/2
• Inside the inner loop, all operations are O(1): checking if a character is in the vowel set, arithmetic operations, and modulo operation
• Therefore, the overall time complexity is O(n²)

Space Complexity: O(1)

The algorithm uses:

• A constant-size set vs containing 5 vowels, which is O(1) space
• A few integer variables (n, ans, vowels, consonants, loop counters), each using O(1) space
• No additional data structures that grow with input size
• Therefore, the overall space complexity is O(1)

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

Common Pitfalls

1. Inefficient Repeated Vowel Checking

A common mistake is checking if a character is a vowel using a list instead of a set, or worse, using multiple if-conditions:

Inefficient approach:

# Using a list (O(n) lookup time)
vowels_list = ['a', 'e', 'i', 'o', 'u']
if s[j] in vowels_list:  # O(n) operation
    vowel_count += 1

# Or using multiple conditions
if s[j] == 'a' or s[j] == 'e' or s[j] == 'i' or s[j] == 'o' or s[j] == 'u':
    vowel_count += 1

Solution: Always use a set for O(1) constant-time lookups when checking membership repeatedly.

2. Integer Overflow with Large Products

When vowel and consonant counts are large, their product might overflow in some languages. While Python handles arbitrary precision integers automatically, this could be an issue in languages like C++ or Java.

Potential issue:

# In languages with fixed integer sizes, this could overflow
if vowel_count * consonant_count % k == 0:  

Solution: Use modular arithmetic properties or check divisibility differently:

# Alternative approach to avoid large products
if vowel_count == consonant_count:
    # Since they're equal, we can check (vowel_count^2) % k
    if (vowel_count * vowel_count) % k == 0:
        beautiful_count += 1

3. Forgetting Edge Cases with k

A subtle pitfall is not considering special values of k, particularly when k is large or has specific prime factorizations.

Issue: When vowel_count = consonant_count = 0 (empty substring), the product is 0, which is divisible by any k > 0. However, the problem specifies non-empty substrings.

Solution: The code correctly starts with substrings of length 1 by using range(start_idx, n), avoiding empty substrings.

4. Redundant Condition Checking

Some might check the beautiful conditions for every iteration, even when it's impossible to satisfy them:

Inefficient approach:

for end_idx in range(start_idx, n):
    # Checking conditions even when substring length is odd
    # (impossible to have equal vowels and consonants)
    if vowel_count == consonant_count:
        ...

Optimization: Skip checking when the substring length is odd:

substring_length = end_idx - start_idx + 1
if substring_length % 2 == 1:
    continue  # Skip odd-length substrings
consonant_count = substring_length - vowel_count
if vowel_count == consonant_count and (vowel_count * consonant_count) % k == 0:
    beautiful_count += 1

5. Case Sensitivity Issues

The problem doesn't specify if the input contains uppercase letters. Failing to handle case sensitivity could lead to incorrect results.

Potential issue:

vowels_set = {'a', 'e', 'i', 'o', 'u'}
if s[j] in vowels_set:  # Won't catch 'A', 'E', etc.

Solution: Either convert the string to lowercase first or include both cases in the set:

# Option 1: Convert to lowercase
s = s.lower()

# Option 2: Include both cases
vowels_set = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}