LeetCode Problem 2947

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String, Enumeration, Number Theory, Prefix Sum

Solution

LeetCode 2947 - Count Beautiful Substrings I

Problem Understanding

We are given a lowercase English string s and a positive integer k. We must count how many non-empty substrings satisfy the definition of a beautiful substring.

For a substring, let:

• vowels be the number of vowel characters (a, e, i, o, u)
• consonants be the number of non-vowel characters

A substring is considered beautiful if two conditions are simultaneously true:

1. The number of vowels equals the number of consonants.
2. The product vowels * consonants is divisible by k.

The task is to return the total number of such substrings.

The input consists of:

• A string s of length between 1 and 1000
• An integer k between 1 and 1000

The output is a single integer representing the number of beautiful substrings.

The constraint n <= 1000 is important. It tells us that an O(n²) solution is feasible because 1000² = 1,000,000, which is manageable. However, an O(n³) solution would be unnecessarily slow because it would examine roughly one billion operations in the worst case.

Several edge cases deserve attention:

• A string containing only consonants can never have equal vowels and consonants.
• A string containing only vowels can never have equal vowels and consonants.
• When k = 1, the divisibility condition is always satisfied, so only the balance condition matters.
• Beautiful substrings must have even length because vowels and consonants must be equal.
• Very short strings may contain no valid substrings at all.

Approaches

Brute Force

The most direct solution is to enumerate every possible substring.

For each starting index, we try every ending index. Once a substring is chosen, we count how many vowels and consonants it contains. If the counts are equal and their product is divisible by k, we increment the answer.

This approach is correct because every substring is examined exactly once and checked against the problem definition.

However, if we recompute vowel and consonant counts from scratch for every substring, the complexity becomes O(n³):

• O(n²) substrings
• O(n) work to count characters inside each substring

This is unnecessarily expensive.

Key Insight

A substring is beautiful when:

vowels = consonants = x

Therefore:

vowels * consonants = x²

The divisibility condition becomes:

x² % k == 0

Since:

length = vowels + consonants = 2x

we can determine whether a substring length is eligible simply by examining:

(length / 2)² % k == 0

Next, we need an efficient way to determine whether a substring has equal vowels and consonants.

Assign:

• +1 for a vowel
• -1 for a consonant

Let prefix[i] be the cumulative sum up to position i.

For any substring:

balance = prefix[r + 1] - prefix[l]

A substring has equal vowels and consonants exactly when:

balance = 0

which means:

prefix[r + 1] = prefix[l]

Thus, we only need to find pairs of indices with equal prefix balances and additionally verify the divisibility condition.

Because n <= 1000, we can enumerate all substrings while maintaining counts incrementally, achieving O(n²) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Recompute vowel and consonant counts for every substring
Optimal	O(n²)	O(1)	Incrementally maintain counts while extending substrings

Algorithm Walkthrough

1. Create a set containing all vowels: {a, e, i, o, u}.
2. Initialize answer = 0.
3. For every starting position left in the string:

• Set vowel_count = 0.
• Set consonant_count = 0.

4. Extend the substring one character at a time using an ending position right.
5. When a new character is added:

• If it is a vowel, increment vowel_count.
• Otherwise increment consonant_count.

6. After updating the counts, check whether:

vowel_count == consonant_count

If not, the substring cannot be beautiful. 7. If the counts are equal, let:

x = vowel_count

Since vowel_count == consonant_count, the product is:

x * x

8. Check:

(x * x) % k == 0

If true, increment the answer. 9. Continue extending the substring until all ending positions have been processed. 10. After all starting positions have been considered, return the accumulated answer.

Why it works

For every possible substring, the algorithm maintains the exact number of vowels and consonants contained within it. A substring is counted only when it satisfies both requirements from the problem statement:

• equal numbers of vowels and consonants
• product divisible by k

Since every substring is examined exactly once and every counted substring satisfies the definition of beauty, the final answer is correct.

Python Solution

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        vowels = {"a", "e", "i", "o", "u"}
        n = len(s)
        answer = 0

        for left in range(n):
            vowel_count = 0
            consonant_count = 0

            for right in range(left, n):
                if s[right] in vowels:
                    vowel_count += 1
                else:
                    consonant_count += 1

                if (
                    vowel_count == consonant_count
                    and (vowel_count * vowel_count) % k == 0
                ):
                    answer += 1

        return answer

The implementation begins by creating a set of vowels for constant time membership checks.

The outer loop selects every possible starting index of a substring. For each starting index, the vowel and consonant counts are reset.

The inner loop progressively extends the substring to the right. Because characters are added one at a time, we only need to update the counts for the newly added character rather than recomputing counts from scratch.

Whenever the vowel and consonant counts become equal, we know both values are the same number x. The divisibility condition therefore simplifies to checking whether x² is divisible by k.

Every valid substring contributes one to the answer, and the final count is returned.

Go Solution

func beautifulSubstrings(s string, k int) int {
    n := len(s)
    answer := 0

    isVowel := func(c byte) bool {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
    }

    for left := 0; left < n; left++ {
        vowels := 0
        consonants := 0

        for right := left; right < n; right++ {
            if isVowel(s[right]) {
                vowels++
            } else {
                consonants++
            }

            if vowels == consonants &&
                (vowels*vowels)%k == 0 {
                answer++
            }
        }
    }

    return answer
}

The Go implementation follows exactly the same logic as the Python version.

A helper function determines whether a character is a vowel. The nested loops enumerate all substrings, while the counts are updated incrementally as the right boundary expands. Since the maximum string length is only 1000, standard Go integers are more than sufficient and there is no risk of overflow.

Worked Examples

Example 1

s = "baeyh"
k = 2

Substring	Vowels	Consonants	Equal?	Product % 2	Counted?
b	0	1	No	-	No
ba	1	1	Yes	1	No
bae	2	1	No	-	No
baey	2	2	Yes	0	Yes
baeyh	2	3	No	-	No
a	1	0	No	-	No
ae	2	0	No	-	No
aey	2	1	No	-	No
aeyh	2	2	Yes	0	Yes
e	1	0	No	-	No
ey	1	1	Yes	1	No
eyh	1	2	No	-	No
y	0	1	No	-	No
yh	0	2	No	-	No
h	0	1	No	-	No

Total beautiful substrings: 2

Example 2

s = "abba"
k = 1

Since every integer is divisible by 1, only the equality condition matters.

Substring	Vowels	Consonants	Counted?
ab	1	1	Yes
ba	1	1	Yes
abba	2	2	Yes

Answer = 3

Example 3

s = "bcdf"
k = 1

Every character is a consonant.

No substring can have equal numbers of vowels and consonants.

Answer = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Two nested loops enumerate all substrings
Space	O(1)	Only a few counters and a vowel set are used

There are O(n²) possible substrings, and each substring is processed incrementally as the right endpoint expands. No auxiliary data structure grows with the input size, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.beautifulSubstrings("baeyh", 2) == 2  # example 1
assert sol.beautifulSubstrings("abba", 1) == 3   # example 2
assert sol.beautifulSubstrings("bcdf", 1) == 0   # example 3

assert sol.beautifulSubstrings("a", 1) == 0      # single vowel
assert sol.beautifulSubstrings("b", 1) == 0      # single consonant

assert sol.beautifulSubstrings("ab", 1) == 1     # smallest valid substring
assert sol.beautifulSubstrings("ab", 2) == 0     # product not divisible by k

assert sol.beautifulSubstrings("ae", 1) == 0     # all vowels
assert sol.beautifulSubstrings("bc", 1) == 0     # all consonants

assert sol.beautifulSubstrings("abab", 1) == 4   # multiple overlapping answers

assert sol.beautifulSubstrings("aabb", 4) == 1   # only whole string works

assert sol.beautifulSubstrings("abcde", 1000) == 0  # very restrictive k

assert sol.beautifulSubstrings("aeioubcdfg", 25) == 1  # balanced full string

Test Summary

Test	Why
("baeyh", 2)	Official example 1
("abba", 1)	Official example 2
("bcdf", 1)	Official example 3
("a", 1)	Single character vowel
("b", 1)	Single character consonant
("ab", 1)	Smallest beautiful substring
("ab", 2)	Divisibility condition fails
("ae", 1)	All vowels
("bc", 1)	All consonants
("abab", 1)	Multiple overlapping valid substrings
("aabb", 4)	Product divisibility check
("abcde", 1000)	Large k value
("aeioubcdfg", 25)	Balanced whole string

Edge Cases

String Contains Only Vowels

A substring can only be beautiful when the numbers of vowels and consonants are equal. If the entire string contains only vowels, every substring will also contain only vowels, making equality impossible.

The implementation naturally handles this because consonant_count never increases, so the equality condition never becomes true.

String Contains Only Consonants

This is the symmetric case of the previous scenario. Every substring contains zero vowels, so no substring can satisfy the balance requirement.

The algorithm correctly returns zero because vowel_count == consonant_count is never satisfied for any non-empty substring.

Large Values of k

When k is large, many balanced substrings fail the divisibility condition even though they have equal numbers of vowels and consonants.

For example, a substring with two vowels and two consonants has product 4. If k = 1000, then 4 % 1000 != 0, so the substring is not beautiful.

The implementation explicitly checks (vowel_count * vowel_count) % k == 0, ensuring that balanced substrings are counted only when the divisibility requirement is also satisfied.

Overlapping Beautiful Substrings

Different beautiful substrings may share many characters. For example, in "abab", both "ab" occurrences and the entire string "abab" are valid.

Because the algorithm enumerates every possible (left, right) pair independently, overlapping substrings are counted separately exactly as required by the problem statement.