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.
- Difficulty: Medium
- Topics: Strings, Hash Table, Math, Prefix Sum, Enumeration
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 10001 <= k <= 1000s consists only of lowercase English letters
Hints for Count Beautiful Substrings I
Hint 1
With
s.length <= 1000you can afford to look at every substring, as long as you do not recount its vowels from scratch.Hint 2
Fix the left end
iand extend the right endjone character at a time, updating a running vowel count.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
- For every start index
i, setv = 0. - For every end index
j >= i, add one tovifs[j]is a vowel; the consonant count isc = (j - i + 1) - v. - If
v == cand(v * c) % k == 0, count the substring. - 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 atn = 1000. yis a consonant here.- A balanced substring always has even length, but both conditions must still hold —
v * cmust be divisible byk, notvalone.
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 resJava
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