Count Beautiful Substrings II

Hard

#2629Time: O(N^2), where N is the length of the string `s`. The two nested loops iterate through all `O(N^2)` substrings, and the check for each is O(1).Space: O(1), as we only use a few variables to store counts, regardless of the input size.

Patterns

Math Number Theory Prefix Sum

Data structures

Hash Table String

Prompt

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.

Example 1:

Input: s = "baeyh", k = 2
Output: 2
Explanation: 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
Explanation: 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
Explanation: There are no beautiful substrings in the given string.

Constraints:

1 <= s.length <= 5 * 10⁴
1 <= k <= 1000
s consists of only English lowercase letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible substring of the given string s. For each substring, we count the vowels and consonants and verify if it meets the two conditions for being 'beautiful'. To avoid a TLE (Time Limit Exceeded) error from a naive O(N^3) implementation, we optimize the counting process.

Algorithm

Initialize a counter ans to 0.
Iterate through the string with a starting index i from 0 to n-1.
For each i, initialize vowels = 0 and consonants = 0.
Start a nested loop for the ending index j from i to n-1.
- Update vowels and consonants based on the character s[j].
- Check if vowels > 0 and vowels == consonants.
- If true, check if (vowels * vowels) % k == 0.
- If both conditions are met, increment ans.
Return ans.

Walkthrough

We can iterate through all possible starting positions i of a substring. For each i, we start another loop for the ending position j from i to the end of the string. As we extend the substring by one character at j, we maintain a running count of vowels and consonants. This allows us to check the conditions for the substring s[i...j] in O(1) time within the inner loop.

The two conditions for a beautiful substring are:

vowels == consonants
(vowels * consonants) % k == 0

If both are true for the current substring, we increment our result counter.

1class Solution {2    private boolean isVowel(char c) {3        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';4    }5 6    public long beautifulSubstrings(String s, int k) {7        long count = 0;8        int n = s.length();9        for (int i = 0; i < n; i++) {10            int vowels = 0;11            int consonants = 0;12            for (int j = i; j < n; j++) {13                if (isVowel(s.charAt(j))) {14                    vowels++;15                } else {16                    consonants++;17                }18                if (vowels > 0 && vowels == consonants) {19                    if ((long)vowels * vowels % k == 0) {20                        count++;21                    }22                }23            }24        }25        return count;26    }27}

This approach is straightforward but its quadratic time complexity makes it too slow for the given constraints.

Complexity

Time

O(N^2), where N is the length of the string `s`. The two nested loops iterate through all `O(N^2)` substrings, and the check for each is O(1).

Space

O(1), as we only use a few variables to store counts, regardless of the input size.

Trade-offs

Pros

Simple to understand and implement.
Low memory usage.

Cons

Inefficient for large inputs, leading to Time Limit Exceeded (TLE).

This optimal solution leverages number theory and prefix sums (differences) to count beautiful substrings in linear time. By transforming the two conditions into properties of prefix states, we can use a hash map to efficiently find matching substrings without iterating through all of them.

Algorithm

Calculate a period based on 4*k. This is done by finding the prime factorization of 4*k and constructing a new number where each prime p with exponent a is replaced by p with exponent ceil(a/2).
Initialize ans = 0, diff = 0.
Initialize a hash map counts to store frequencies of (diff, index % period) states.
Put the initial state for an index p = -1 into the map: diff = 0, rem = (-1 % period + period) % period. The count for state (0, rem) is 1.
Iterate through the string with index j from 0 to n-1:
- Update diff based on s[j] (+1 for vowel, -1 for consonant).
- Calculate rem = j % period.
- Form the state key from (diff, rem).
- Get the count of this state from the counts map and add it to ans.
- Increment the count for the current state in the map.
Return ans.

Walkthrough

The problem's conditions can be rephrased to enable a more efficient counting method. Let's analyze a substring s[i...j].

vowels == consonants: We can model this by assigning +1 to vowels and -1 to consonants. A substring satisfies this condition if the sum of these values over its characters is 0. Using a prefix difference array diff, where diff[x] is the net sum for the prefix s[0...x], this condition becomes diff[j] == diff[i-1].
(vowels * consonants) % k == 0: Since vowels == consonants, the substring length L = j - i + 1 must be even, with vowels = L / 2. The condition becomes (L/2)^2 % k == 0, which simplifies to L^2 % (4*k) == 0. This number theory condition holds if and only if L is a multiple of a specific number, which we'll call period. This period is derived from the prime factorization of 4*k. The condition L % period == 0 is equivalent to (j - (i-1)) % period == 0, which means j % period == (i-1) % period.

Combining these, we need to find pairs of indices (p, j) (where p = i-1) that satisfy diff[j] == diff[p] and j % period == p % period. We can iterate through the string, tracking the state (diff, index % period). A hash map stores the frequencies of these states, allowing us to find the number of valid starting points for each ending point j in O(1) time.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    private boolean isVowel(char c) {6        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';7    }8 9    private int calculatePeriod(int k) {10        long num = 4L * k;11        int period = 1;12        for (long i = 2; i * i <= num; i++) {13            if (num % i == 0) {14                int count = 0;15                while (num % i == 0) {16                    count++;17                    num /= i;18                }19                for (int j = 0; j < (count + 1) / 2; j++) {20                    period *= i;21                }22            }23        }24        if (num > 1) {25            period *= num;26        }27        return period;28    }29 30    public long beautifulSubstrings(String s, int k) {31        int period = calculatePeriod(k);32        int n = s.length();33        Map<String, Integer> counts = new HashMap<>();34        35        int initialRem = (-1 % period + period) % period;36        counts.put("0:" + initialRem, 1);37 38        long ans = 0;39        int diff = 0;40 41        for (int j = 0; j < n; j++) {42            if (isVowel(s.charAt(j))) {43                diff++;44            } else {45                diff--;46            }47 48            int rem = j % period;49            String key = diff + ":" + rem;50            51            int prevCount = counts.getOrDefault(key, 0);52            ans += prevCount;53            54            counts.put(key, prevCount + 1);55        }56 57        return ans;58    }59}

Complexity

Time

O(N + sqrt(K)), where N is the string length. Calculating the `period` takes `O(sqrt(K))`. The main loop is `O(N)` with `O(1)` average time for hash map operations.

Space

O(N). The hash map can store up to N+1 distinct states in the worst case.

Trade-offs

Pros

Highly efficient with linear time complexity.
Scales well for large inputs.

Cons

The logic is complex and relies on number theory, making it less intuitive.
Requires careful implementation of state representation and modular arithmetic.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem