Scale Engineer

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
MathNumber TheoryPrefix Sum
Data structures
Hash TableString

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 * 104
  • 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:

  1. vowels == consonants
  2. (vowels * consonants) % k == 0

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

class Solution {    private boolean isVowel(char c) {        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';    }     public long beautifulSubstrings(String s, int k) {        long count = 0;        int n = s.length();        for (int i = 0; i < n; i++) {            int vowels = 0;            int consonants = 0;            for (int j = i; j < n; j++) {                if (isVowel(s.charAt(j))) {                    vowels++;                } else {                    consonants++;                }                if (vowels > 0 && vowels == consonants) {                    if ((long)vowels * vowels % k == 0) {                        count++;                    }                }            }        }        return count;    }}

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).

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 →

Next problem