Problem

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

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

Input: s = "abba", k = 1
Output: 3
Explanation: There are 3 beautiful substrings in the given string.
- Substring "_ab_ ba", vowels = 1 (["a"]), consonants = 1 (["b"]).
- Substring "ab _ba_ ", 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

1
2
3

Input: s = "bcdf", k = 1
Output: 0
Explanation: There are no beautiful substrings in the given string.

Constraints

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

Solution

Method 1 – Prefix Sum and Hash Map (Optimized for Large k) 1

Intuition

We want to count substrings where the number of vowels equals the number of consonants, and their product is divisible by k. For large k, we can optimize by only considering substring lengths that are multiples of k and use prefix sums to efficiently count valid substrings.

Approach

  1. Define a set of vowels for quick lookup.
  2. For each possible substring length L (L % k == 0), iterate over all substrings of length L.
  3. For each substring, use prefix sums to get the number of vowels and consonants.
  4. If vowels == consonants and vowels * consonants % k == 0, count the substring.
  5. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int beautifulSubstrings(string s, int k) {
        unordered_set<char> vowels = {'a','e','i','o','u'};
        int n = s.size(), ans = 0;
        vector<int> vcnt(n+1), ccnt(n+1);
        for (int i = 0; i < n; ++i) {
            vcnt[i+1] = vcnt[i] + vowels.count(s[i]);
            ccnt[i+1] = ccnt[i] + (!vowels.count(s[i]));
        }
        for (int len = 2; len <= n; len += 2) {
            if ((len/2)*(len/2) % k != 0) continue;
            for (int i = 0; i + len <= n; ++i) {
                int v = vcnt[i+len] - vcnt[i];
                int c = ccnt[i+len] - ccnt[i];
                if (v == c && v * c % k == 0) ans++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func beautifulSubstrings(s string, k int) int {
    vowels := map[byte]bool{'a':true,'e':true,'i':true,'o':true,'u':true}
    n, ans := len(s), 0
    vcnt := make([]int, n+1)
    ccnt := make([]int, n+1)
    for i := 0; i < n; i++ {
        if vowels[s[i]] {
            vcnt[i+1] = vcnt[i] + 1
            ccnt[i+1] = ccnt[i]
        } else {
            vcnt[i+1] = vcnt[i]
            ccnt[i+1] = ccnt[i] + 1
        }
    }
    for l := 2; l <= n; l += 2 {
        if (l/2)*(l/2)%k != 0 {
            continue
        }
        for i := 0; i+l <= n; i++ {
            v := vcnt[i+l] - vcnt[i]
            c := ccnt[i+l] - ccnt[i]
            if v == c && v*c%k == 0 {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int beautifulSubstrings(String s, int k) {
        Set<Character> vowels = Set.of('a','e','i','o','u');
        int n = s.length(), ans = 0;
        int[] vcnt = new int[n+1], ccnt = new int[n+1];
        for (int i = 0; i < n; ++i) {
            vcnt[i+1] = vcnt[i] + (vowels.contains(s.charAt(i)) ? 1 : 0);
            ccnt[i+1] = ccnt[i] + (vowels.contains(s.charAt(i)) ? 0 : 1);
        }
        for (int len = 2; len <= n; len += 2) {
            if ((len/2)*(len/2) % k != 0) continue;
            for (int i = 0; i + len <= n; ++i) {
                int v = vcnt[i+len] - vcnt[i];
                int c = ccnt[i+len] - ccnt[i];
                if (v == c && v * c % k == 0) ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun beautifulSubstrings(s: String, k: Int): Int {
        val vowels = setOf('a','e','i','o','u')
        val n = s.length
        val vcnt = IntArray(n+1)
        val ccnt = IntArray(n+1)
        for (i in 0 until n) {
            vcnt[i+1] = vcnt[i] + if (s[i] in vowels) 1 else 0
            ccnt[i+1] = ccnt[i] + if (s[i] in vowels) 0 else 1
        }
        var ans = 0
        for (len in 2..n step 2) {
            if ((len/2)*(len/2) % k != 0) continue
            for (i in 0..n-len) {
                val v = vcnt[i+len] - vcnt[i]
                val c = ccnt[i+len] - ccnt[i]
                if (v == c && v * c % k == 0) ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        n = len(s)
        vcnt = [0] * (n+1)
        ccnt = [0] * (n+1)
        for i in range(n):
            vcnt[i+1] = vcnt[i] + (s[i] in vowels)
            ccnt[i+1] = ccnt[i] + (s[i] not in vowels)
        ans = 0
        for l in range(2, n+1, 2):
            if (l//2)*(l//2) % k != 0:
                continue
            for i in range(n-l+1):
                v = vcnt[i+l] - vcnt[i]
                c = ccnt[i+l] - ccnt[i]
                if v == c and v * c % k == 0:
                    ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn beautiful_substrings(s: String, k: i32) -> i32 {
        let vowels = [b'a', b'e', b'i', b'o', b'u'];
        let n = s.len();
        let s = s.as_bytes();
        let mut vcnt = vec![0; n+1];
        let mut ccnt = vec![0; n+1];
        for i in 0..n {
            vcnt[i+1] = vcnt[i] + if vowels.contains(&s[i]) { 1 } else { 0 };
            ccnt[i+1] = ccnt[i] + if vowels.contains(&s[i]) { 0 } else { 1 };
        }
        let mut ans = 0;
        for len in (2..=n).step_by(2) {
            if (len/2)*(len/2) % k != 0 { continue; }
            for i in 0..=n-len {
                let v = vcnt[i+len] - vcnt[i];
                let c = ccnt[i+len] - ccnt[i];
                if v == c && v * c % k == 0 {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    beautifulSubstrings(s: string, k: number): number {
        const vowels = new Set(['a','e','i','o','u']);
        const n = s.length;
        const vcnt = new Array(n+1).fill(0);
        const ccnt = new Array(n+1).fill(0);
        for (let i = 0; i < n; ++i) {
            vcnt[i+1] = vcnt[i] + (vowels.has(s[i]) ? 1 : 0);
            ccnt[i+1] = ccnt[i] + (vowels.has(s[i]) ? 0 : 1);
        }
        let ans = 0;
        for (let len = 2; len <= n; len += 2) {
            if ((len/2)*(len/2) % k !== 0) continue;
            for (let i = 0; i + len <= n; ++i) {
                const v = vcnt[i+len] - vcnt[i];
                const c = ccnt[i+len] - ccnt[i];
                if (v === c && v * c % k === 0) ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of s, as we check all possible substrings of even length.
  • 🧺 Space complexity: O(n), for the prefix sum arrays.