Scale Engineer

Count Beautiful Substrings I

Med
#2627Time: O(n²), where n is the length of the string `s`. The two nested loops iterate through all possible substrings, and the work inside the inner loop is constant time.Space: O(1)
Patterns
MathEnumerationNumber 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 <= 1000
  • 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 non-empty substring of the given string s. For each substring, we count the number of vowels and consonants and then check if it satisfies the two conditions for being beautiful.

Algorithm

  • Initialize a variable count to 0 to store the number of beautiful substrings.
  • Iterate through the string s with an outer loop using index i from 0 to n-1, where n is the length of s. This index i will be the starting point of a substring.
  • Inside the outer loop, initialize vowels = 0 and consonants = 0.
  • Start an inner loop with index j from i to n-1. This index j will be the ending point of the substring s[i..j].
  • In the inner loop, check the character s.charAt(j). If it's a vowel, increment vowels; otherwise, increment consonants.
  • After updating the counts, check if the two conditions for a beautiful substring are met:
    1. vowels == consonants
    2. (vowels * consonants) % k == 0
  • If both conditions are true, increment the count.
  • After the loops complete, return the total count.

Walkthrough

We can generate all substrings by using two nested loops. The outer loop fixes the starting index i of the substring, and the inner loop iterates from i to the end of the string, fixing the ending index j.

For each substring s[i..j], instead of recounting vowels and consonants from scratch, we can maintain running counts. As we extend the substring by one character (by incrementing j), we update the vowels and consonants counts in O(1) time. After each update, we check if the current substring is beautiful.

This avoids a third loop for counting, reducing the complexity from O(n³) to O(n²).

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

Complexity

Time

O(n²), where n is the length of the string `s`. The two nested loops iterate through all possible substrings, and the work inside the inner loop is constant time.

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal extra space.

Cons

  • The time complexity is quadratic, which might be too slow for very large input strings (though it passes for the given constraints).

Solutions

class Solution {public  int beautifulSubstrings(String s, int k) {    int n = s.length();    int[] vs = new int[26];    for (char c : "aeiou".toCharArray()) {      vs[c - 'a'] = 1;    }    int ans = 0;    for (int i = 0; i < n; ++i) {      int vowels = 0;      for (int j = i; j < n; ++j) {        vowels += vs[s.charAt(j) - 'a'];        int consonants = j - i + 1 - vowels;        if (vowels == consonants && vowels * consonants % k == 0) {          ++ans;        }      }    }    return ans;  }}

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