Count Beautiful Substrings I

Medium
1761.

Count Beautiful Substrings I

Count Beautiful Substrings I is a medium coding problem on strings, hash table and math, asked in Amazon interviews.

You are given a string s of lowercase letters and a positive integer k.

For a string, let vowels be the number of vowels in it (a, e, i, o, u) and consonants the number of other letters. A string is beautiful when:

  • vowels == consonants, and
  • (vowels * consonants) % k == 0.

Return the number of non-empty substrings of s that are beautiful. Substrings at different positions count separately even if they read the same.

Example 1

Input
s = "baeyh", k = 2
Output
2
Explanation
"baey" has 2 vowels and 2 consonants and 2 * 2 = 4 is divisible by 2; so is "aeyh". No other substring qualifies.

Example 2

Input
s = "abba", k = 1
Output
3
Explanation
"ab", "ba" (the last two letters) and "abba" each balance vowels and consonants, and every product is divisible by 1.

Example 3

Input
s = "bcdf", k = 1
Output
0
Explanation
There are no vowels, so no non-empty substring can balance.

Constraints

  • 1 <= s.length <= 1000
  • 1 <= k <= 1000
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var beautifulSubstrings = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Beautiful Substrings I — Problem & Solution

Count Beautiful Substrings I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Beautiful Substrings I is a medium coding problem on strings, hash table and math, asked in Amazon interviews.

Problem statement

You are given a string s of lowercase letters and a positive integer k.

For a string, let vowels be the number of vowels in it (a, e, i, o, u) and consonants the number of other letters. A string is beautiful when:

  • vowels == consonants, and
  • (vowels * consonants) % k == 0.

Return the number of non-empty substrings of s that are beautiful. Substrings at different positions count separately even if they read the same.

Example 1

Input: s = "baeyh", k = 2
Output: 2
Explanation: "baey" has 2 vowels and 2 consonants and 2 * 2 = 4 is divisible by 2; so is "aeyh". No other substring qualifies.

Example 2

Input: s = "abba", k = 1
Output: 3
Explanation: "ab", "ba" (the last two letters) and "abba" each balance vowels and consonants, and every product is divisible by 1.

Example 3

Input: s = "bcdf", k = 1
Output: 0
Explanation: There are no vowels, so no non-empty substring can balance.

Constraints

  • 1 <= s.length <= 1000
  • 1 <= k <= 1000
  • s consists only of lowercase English letters

Hints for Count Beautiful Substrings I

  1. Hint 1

    With s.length <= 1000 you can afford to look at every substring, as long as you do not recount its vowels from scratch.

  2. Hint 2

    Fix the left end i and extend the right end j one character at a time, updating a running vowel count.

  3. Hint 3

    The consonant count is the length minus the vowel count; test both conditions for each (i, j).

How to solve Count Beautiful Substrings I

There are only about half a million substrings at the largest size, so enumerate them all — but grow each one from a fixed start so the vowel count updates in O(1) per step.

Approach

  1. For every start index i, set v = 0.
  2. For every end index j >= i, add one to v if s[j] is a vowel; the consonant count is c = (j - i + 1) - v.
  3. If v == c and (v * c) % k == 0, count the substring.
  4. Return the total.

Why it works

Each non-empty substring is s[i..j] for exactly one pair i <= j, and the running count makes v the exact vowel count of s[i..j] when it is tested — so every substring is checked once against the definition.

Complexity

  • Time — O(n^2)
  • Space — O(1)

Pitfalls

  • Recounting the vowels inside the double loop makes it O(n^3), too slow at n = 1000.
  • y is a consonant here.
  • A balanced substring always has even length, but both conditions must still hold — v * c must be divisible by k, not v alone.

Reference solution

Python

def beautifulSubstrings(s: str, k: int) -> int:
    n = len(s)
    res = 0
    for i in range(n):
        v = 0
        for j in range(i, n):
            if s[j] in "aeiou":
                v += 1
            c = j - i + 1 - v
            if v == c and (v * c) % k == 0:
                res += 1
    return res

Java

public static int beautifulSubstrings(String s, int k) {
    int n = s.length(), res = 0;
    for (int i = 0; i < n; i++) {
        int v = 0;
        for (int j = i; j < n; j++) {
            if ("aeiou".indexOf(s.charAt(j)) >= 0) v++;
            int c = j - i + 1 - v;
            if (v == c && (v * c) % k == 0) res++;
        }
    }
    return res;
}

C++

int beautifulSubstrings(string s, int k) {
    int n = s.size(), res = 0;
    for (int i = 0; i < n; i++) {
        int v = 0;
        for (int j = i; j < n; j++) {
            char ch = s[j];
            if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') v++;
            int c = j - i + 1 - v;
            if (v == c && (v * c) % k == 0) res++;
        }
    }
    return res;
}

JavaScript

var beautifulSubstrings = function(s, k) {
    var n = s.length, res = 0;
    for (var i = 0; i < n; i++) {
        var v = 0;
        for (var j = i; j < n; j++) {
            if ("aeiou".indexOf(s[j]) >= 0) v++;
            var c = j - i + 1 - v;
            if (v === c && (v * c) % k === 0) res++;
        }
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets