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 <= 1000
  • 1 <= k <= 1000
  • s consists of only English lowercase letters.

Solution

Method 1 – Prefix Sum and Hash Map 1

Intuition

We want to count substrings where the number of vowels equals the number of consonants, and their product is divisible by k. We can use prefix sums to track the difference between vowels and consonants, and a hash map to count occurrences of each (diff, vowel count) pair. For each position, we check all previous positions with the same diff and test the product divisibility.

Approach

  1. Define a set of vowels for quick lookup.
  2. Use prefix sums to track the difference between vowels and consonants and the count of vowels up to each position.
  3. Use a hash map to store for each (diff, vowel count) the list of indices where this occurs.
  4. For each end index, for all start indices with the same diff, check if the substring’s vowel and consonant counts are equal and their product is divisible by k.
  5. Count all such substrings.

Code

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

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> diff(n+1), vcnt(n+1);
        for (int i = 0; i < n; ++i) {
            vcnt[i+1] = vcnt[i] + vowels.count(s[i]);
            diff[i+1] = vcnt[i+1] - (i+1 - vcnt[i+1]);
        }
        unordered_map<int, vector<int>> mp;
        mp[0].push_back(0);
        for (int i = 1; i <= n; ++i) {
            for (int j : mp[diff[i]]) {
                int v = vcnt[i] - vcnt[j];
                int c = (i-j) - v;
                if (v == c && v * c % k == 0 && v > 0) ans++;
            }
            mp[diff[i]].push_back(i);
        }
        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

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
    diff := make([]int, n+1)
    vcnt := make([]int, n+1)
    for i := 0; i < n; i++ {
        if vowels[s[i]] {
            vcnt[i+1] = vcnt[i] + 1
        } else {
            vcnt[i+1] = vcnt[i]
        }
        diff[i+1] = vcnt[i+1] - (i+1 - vcnt[i+1])
    }
    mp := map[int][]int{0: {0}}
    for i := 1; i <= n; i++ {
        for _, j := range mp[diff[i]] {
            v := vcnt[i] - vcnt[j]
            c := (i-j) - v
            if v == c && v*c%k == 0 && v > 0 {
                ans++
            }
        }
        mp[diff[i]] = append(mp[diff[i]], i)
    }
    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 {
    public int beautifulSubstrings(String s, int k) {
        Set<Character> vowels = Set.of('a','e','i','o','u');
        int n = s.length(), ans = 0;
        int[] diff = new int[n+1], vcnt = new int[n+1];
        for (int i = 0; i < n; ++i) {
            vcnt[i+1] = vcnt[i] + (vowels.contains(s.charAt(i)) ? 1 : 0);
            diff[i+1] = vcnt[i+1] - (i+1 - vcnt[i+1]);
        }
        Map<Integer, List<Integer>> mp = new HashMap<>();
        mp.computeIfAbsent(0, z->new ArrayList<>()).add(0);
        for (int i = 1; i <= n; ++i) {
            for (int j : mp.getOrDefault(diff[i], List.of())) {
                int v = vcnt[i] - vcnt[j];
                int c = (i-j) - v;
                if (v == c && v * c % k == 0 && v > 0) ans++;
            }
            mp.computeIfAbsent(diff[i], z->new ArrayList<>()).add(i);
        }
        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

class Solution {
    fun beautifulSubstrings(s: String, k: Int): Int {
        val vowels = setOf('a','e','i','o','u')
        val n = s.length
        val diff = IntArray(n+1)
        val vcnt = IntArray(n+1)
        var ans = 0
        for (i in 0 until n) {
            vcnt[i+1] = vcnt[i] + if (s[i] in vowels) 1 else 0
            diff[i+1] = vcnt[i+1] - (i+1 - vcnt[i+1])
        }
        val mp = mutableMapOf(0 to mutableListOf(0))
        for (i in 1..n) {
            for (j in mp[diff[i]] ?: emptyList()) {
                val v = vcnt[i] - vcnt[j]
                val c = (i-j) - v
                if (v == c && v * c % k == 0 && v > 0) ans++
            }
            mp.getOrPut(diff[i]) { mutableListOf() }.add(i)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        n = len(s)
        diff = [0] * (n+1)
        vcnt = [0] * (n+1)
        for i in range(n):
            vcnt[i+1] = vcnt[i] + (s[i] in vowels)
            diff[i+1] = vcnt[i+1] - ((i+1) - vcnt[i+1])
        from collections import defaultdict
        mp = defaultdict(list)
        mp[0].append(0)
        ans = 0
        for i in range(1, n+1):
            for j in mp[diff[i]]:
                v = vcnt[i] - vcnt[j]
                c = (i-j) - v
                if v == c and v * c % k == 0 and v > 0:
                    ans += 1
            mp[diff[i]].append(i)
        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
29
30

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 diff = vec![0; n+1];
        let mut vcnt = vec![0; n+1];
        for i in 0..n {
            vcnt[i+1] = vcnt[i] + if vowels.contains(&s[i]) { 1 } else { 0 };
            diff[i+1] = vcnt[i+1] - ((i+1) as i32 - vcnt[i+1]);
        }
        use std::collections::HashMap;
        let mut mp: HashMap<i32, Vec<usize>> = HashMap::new();
        mp.entry(0).or_default().push(0);
        let mut ans = 0;
        for i in 1..=n {
            if let Some(lst) = mp.get(&diff[i]) {
                for &j in lst {
                    let v = vcnt[i] - vcnt[j];
                    let c = (i-j) as i32 - v;
                    if v == c && v * c % k == 0 && v > 0 {
                        ans += 1;
                    }
                }
            }
            mp.entry(diff[i]).or_default().push(i);
        }
        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

class Solution {
    beautifulSubstrings(s: string, k: number): number {
        const vowels = new Set(['a','e','i','o','u']);
        const n = s.length;
        const diff = new Array(n+1).fill(0);
        const vcnt = new Array(n+1).fill(0);
        for (let i = 0; i < n; ++i) {
            vcnt[i+1] = vcnt[i] + (vowels.has(s[i]) ? 1 : 0);
            diff[i+1] = vcnt[i+1] - ((i+1) - vcnt[i+1]);
        }
        const mp = new Map<number, number[]>();
        mp.set(0, [0]);
        let ans = 0;
        for (let i = 1; i <= n; ++i) {
            for (const j of mp.get(diff[i]) ?? []) {
                const v = vcnt[i] - vcnt[j];
                const c = (i-j) - v;
                if (v === c && v * c % k === 0 && v > 0) ans++;
            }
            if (!mp.has(diff[i])) mp.set(diff[i], []);
            mp.get(diff[i])!.push(i);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of s, due to checking all pairs with the same diff.
  • 🧺 Space complexity: O(n^2), for storing all prefix pairs in the hash map.