Count Beautiful Substrings I - Practice Coding Problems

Count Beautiful Substrings I - Problem

Hash Table Math String Enumeration Number Theory Prefix Sum Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "baae", k = 2

› Output: 2

💡 Note: Beautiful substrings are "ba" (1 vowel, 1 consonant, 1*1=1, but we need (1*1)%2=0 which is false) and "baae" (3 vowels, 1 consonant - not equal). Actually "ba" has 1 vowel 'a' and 1 consonant 'b', and (1*1)%2=1≠0. Let me recalculate: "ae" has 2 vowels, 0 consonants (not equal). "aa" has 2 vowels, 0 consonants (not equal). Only "ba" and "aae" need checking. "ba": 1v,1c, (1*1)%2=1≠0. Wait, let me be more systematic with "baae": substrings with equal vowels and consonants are "ba" (1v,1c) and none others work. (1*1)%2=1≠0, so actually 0 beautiful substrings for this case.

Example 2 — Simple Beautiful

$ Input: s = "abab", k = 1

› Output: 2

💡 Note: Beautiful substrings: "ab" at positions 0-1 (1 vowel, 1 consonant, 1*1=1, 1%1=0 ✓), "ba" at positions 1-2 (1 vowel, 1 consonant, 1*1=1, 1%1=0 ✓), "ab" at positions 2-3 (1 vowel, 1 consonant, 1*1=1, 1%1=0 ✓), and "abab" (2 vowels, 2 consonants, 2*2=4, 4%1=0 ✓). Total = 4.

Example 3 — No Beautiful Substrings

$ Input: s = "abc", k = 3

› Output: 0

💡 Note: No substring has equal vowels and consonants: "a"(1v,0c), "b"(0v,1c), "c"(0v,1c), "ab"(1v,1c), "bc"(0v,2c), "abc"(1v,2c). Only "ab" has equal counts but (1*1)%3=1≠0, so no beautiful substrings.

Constraints

1 ≤ s.length ≤ 1000
1 ≤ k ≤ 1000
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String with vowels and consonants, divisibility factor k

Check Conditions

Find substrings with equal vowels/consonants AND product divisible by k

Count Results

Return total number of beautiful substrings

Key Takeaway

🎯 Key Insight: Beautiful substrings require perfect balance AND mathematical harmony with k

Asked in

G Google 25 M Microsoft 18 a Amazon 15 F Facebook 12

The key insight is that a beautiful substring needs both equal vowels/consonants AND their product divisible by k. The optimized approach uses running counts to avoid recalculating character frequencies. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Hash Map	O(n²)	O(n)	Use prefix difference and hash map to find matching patterns
Brute Force	O(n³)	O(1)	Check all possible substrings for both conditions
Optimized with Running Counts	O(n²)	O(1)	Use running vowel and consonant counts to avoid recalculating

Prefix Sum with Hash Map — Algorithm Steps

Step 1: Convert string to +1/-1 array (vowel/consonant)
Step 2: Calculate prefix sums and store in hash map
Step 3: For matching prefix sums, check if substring length satisfies divisibility

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to +1/-1

Vowels become +1, consonants become -1

Calculate Prefix Sums

Running sum helps identify balanced substrings

Find Equal Sums

Same prefix sum means balanced substring between positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

int solution(char* s, int k) {
    int count = 0;
    int n = strlen(s);
    
    // Use simpler O(n²) approach for C implementation
    for (int i = 0; i < n; i++) {
        int vowels = 0;
        int consonants = 0;
        
        for (int j = i; j < n; j++) {
            if (isVowel(s[j])) {
                vowels++;
            } else {
                consonants++;
            }
            
            if (vowels == consonants && vowels > 0 && (vowels * consonants) % k == 0) {
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char s[1001];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n) for prefix sum calculation, but checking divisibility for all matching pairs can be O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map stores up to n prefix sum values and their positions

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

340 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler