Count Beautiful Substrings II — Editorial

Opening the reading…

Intuitionthe product condition is really a length condition

Give each vowel a value of +1 and each consonant a value of -1. For a substring, the sum of these values is zero exactly when its vowel count equals its consonant count. If both counts are x, the substring has length 2x and its product condition becomes x squared divisible by k.

The useful number-theoretic fact is that there is a smallest positive integer d such that d squared is divisible by k, and every valid x is a multiple of d. Therefore a substring is beautiful exactly when its prefix-difference sum is zero and its length is divisible by 2d.

Let prefix[i] be the difference after the first i characters. A substring from i to j has equal vowel and consonant counts when prefix[i] equals prefix[j]. Its length is j - i, so requiring divisibility by 2d is the same as requiring i and j to have the same remainder modulo 2d. Each prefix position can therefore be grouped by two facts: its difference and its position remainder.

The two hashmap fields encode both required conditions.

Approach

Find the smallest positive d whose square is divisible by k by factoring k and raising each prime factor to the ceiling of half its exponent; this compresses all possible valid balances into the statement that x must be a multiple of d.

Set mod to 2d, because a balanced substring with x vowels and x consonants has length 2x, and x being a multiple of d is exactly the same as its length being a multiple of mod.

Start with prefix difference zero at position 0 and record that position in a frequency map; without the empty prefix, substrings beginning at the first character would never be counted.

Scan the string and update the difference by +1 for a vowel and -1 for a consonant; equal differences at two positions are precisely what makes the intervening substring balanced.

For the current position i, look up the count for the key consisting of the current difference and i modulo mod, then add that count to the answer; every earlier matching key supplies one valid starting position.

Insert the current key after querying it, so a prefix position is never paired with itself and every counted substring is non-empty.

Complexityone scan after a constant-size factorization

MEASURE	BOUND	WHY
Time	O(n + sqrt(k))	Factoring k tries divisors up to sqrt(k), and the string scan performs one constant-time map lookup and insertion per character. No substring is examined more than once because each pair is counted when its later prefix position is processed.
Space	O(n) extra	The map stores at most one entry for each scanned prefix position. The returned count is required output and is excluded from working space; the extra bound remains O(n) in the worst case when all prefix keys are distinct.

Here n is the string length and d is the smallest positive integer whose square is divisible by k. The factorization of k takes O(sqrt(k)) time, which is at most constant-sized under k <= 1000.

Annotated solutionC++ · prefix hash map · the version to write from memory

CPPFactor k, then count matching prefix-difference and position-remainder keys in one pass.

#include <string>
#include <unordered_map>
using namespace std;

class Solution {
public:
    long long beautifulSubstrings(string s, int k) {
        int d = 1;
        int value = k;

        for (int prime = 2; prime * prime <= value; ++prime) {
            if (value % prime != 0) continue;

            int exponent = 0;
            while (value % prime == 0) {
                value /= prime;
                ++exponent;
            }

            for (int power = 0; power < (exponent + 1) / 2; ++power)
                d *= prime;
        }

        if (value > 1)
            d *= value;

        int mod = 2 * d;
        unordered_map<long long, long long> frequency;
        long long answer = 0;
        int difference = 0;

        auto keyOf = [n = static_cast<int>(s.size()), mod](int diff, int position) {
            return static_cast<long long>(diff + n) * mod + position % mod;
        };

        frequency[keyOf(0, 0)] = 1;

        for (int i = 0; i < static_cast<int>(s.size()); ++i) {
            char c = s[i];
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
                ++difference;
            else
                --difference;

            int position = i + 1;
            long long key = keyOf(difference, position);
            answer += frequency[key];
            ++frequency[key];
        }

        return answer;
    }
};

The factorization computes d prime by prime. If k contains a prime p to exponent e, x squared contains p to exponent 2 times the exponent of p in x, so x needs at least ceiling of e divided by 2 copies of p. The key packs the difference and the position remainder into one integer; adding n shifts every possible difference into a non-negative range before packing.