01. Balancing Consonants and Vowels Ratio

✅ GFG solution to the Balancing Consonants and Vowels Ratio problem: count balanced substrings with equal vowels and consonants using prefix sum technique. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

You are given an array of strings arr[], where each arr[i] consists of lowercase English alphabets. Your task is to find the number of balanced strings in arr[] which can be formed by concatenating one or more contiguous strings of arr[].

A balanced string contains an equal number of vowels and consonants.

📘 Examples

Example 1

Input: arr[] = ["aeio", "aa", "bc", "ot", "cdbd"]
Output: 4
Explanation: arr[0..4], arr[1..2], arr[1..3], arr[3..3] are the balanced substrings 
with equal consonants and vowels.

Example 2

Input: arr[] = ["ab", "be"]
Output: 3
Explanation: arr[0..0], arr[0..1], arr[1..1] are the balanced substrings 
with equal consonants and vowels.

Example 3

Input: arr[] = ["tz", "gfg", "ae"]
Output: 0
Explanation: There is no such balanced substring present in arr[] 
with equal consonants and vowels.

🔒 Constraints

$1 \le \text{arr.size()} \le 10^5$
$1 \le \text{arr}[i]\text{.size()} \le 10^5$
Total number of lowercase English characters in arr[] is lesser than $10^5$

✅ My Approach

The optimal approach uses the Prefix Sum technique with a Hash Map to efficiently count balanced substrings:

Prefix Sum + Hash Map

Core Insight:
- For a substring to be balanced, the number of vowels must equal the number of consonants.
- We can represent this as: vowels - consonants = 0
- Assign +1 for vowels and -1 for consonants, then find subarrays with sum = 0.
Algorithm Steps:
- Initialize a hash map with {0: 1} to handle subarrays starting from index 0.
- For each string in the array, calculate its score (vowels count - consonants count).
- Maintain a running sum of scores as we process each string.
- If the current sum has been seen before, it means there are subarrays ending at the current position that have a net balance of 0.
- Add the frequency of the current sum to the result and increment its count in the hash map.
Key Operations:
- Calculate score for each string: +1 for each vowel, -1 for each consonant.
- Use prefix sum to track cumulative balance.
- Count occurrences of each prefix sum to find balanced subarrays.
Why This Works:
- If prefixSum[j] == prefixSum[i] for j > i, then the subarray from i+1 to j has sum = 0.
- This means equal vowels and consonants in that subarray.

📝 Time and Auxiliary Space Complexity

Expected Time Complexity: O(n*m), where n is the number of strings and m is the average length of strings. We process each character exactly once to calculate string scores, then perform O(1) hash map operations for each string.
Expected Auxiliary Space Complexity: O(n), where n is the number of strings. In the worst case, we store one entry per string in the hash map when all prefix sums are distinct.

🧑‍💻 Code (C++)

class Solution {
public:
    int countBalanced(vector<string>& arr) {
        int res = 0, sum = 0;
        unordered_map<int, int> mp{{0, 1}};
        for (string& s : arr) {
            int score = 0;
            for (char c : s) score += (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') ? 1 : -1;
            res += mp[sum += score]++;
        }
        return res;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Bit Manipulation Approach

💡 Algorithm Steps:

Use bitwise operations to check vowels faster using lookup table.
Pre-compute vowel mask for O(1) vowel checking.
Single pass with optimized character classification.
Accumulate prefix sums with direct map access.

class Solution {
public:
    int countBalanced(vector<string>& arr) {
        int vowels = (1 << ('a' - 'a')) | (1 << ('e' - 'a')) | (1 << ('i' - 'a')) | (1 << ('o' - 'a')) | (1 << ('u' - 'a'));
        int res = 0, sum = 0;
        unordered_map<int, int> mp{{0, 1}};
        for (auto& s : arr) {
            for (char c : s) sum += (vowels & (1 << (c - 'a'))) ? 1 : -1;
            res += mp[sum]++;
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n*m) - n strings, m average length
Auxiliary Space: 💾 O(n) - HashMap for prefix sums

✅ Why This Approach?

Faster vowel checking using bit operations.
Eliminates multiple character comparisons.
Cache-friendly single bit operation.

📊 3️⃣ Array-Based Frequency

💡 Algorithm Steps:

Use array instead of hash map for better cache performance.
Offset negative indices to handle negative prefix sums.
Direct array access for frequency counting.
Optimized memory access pattern.

class Solution {
public:
    int countBalanced(vector<string>& arr) {
        vector<int> freq(200001, 0);
        int offset = 100000, res = 0, sum = offset;
        freq[offset] = 1;
        for (auto& s : arr) {
            for (char c : s) sum += (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') ? 1 : -1;
            res += freq[sum]++;
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n*m) - Linear traversal
Auxiliary Space: 💾 O(1) - Fixed size array

✅ Why This Approach?

Better cache performance than hash map.
Constant time array access.
No hash collision overhead.

📊 4️⃣ Lambda-Based Compact

💡 Algorithm Steps:

Use lambda for inline vowel checking.
Range-based loops for cleaner syntax.
Minimal variable declarations.
Compact single-expression logic.

class Solution {
public:
    int countBalanced(vector<string>& arr) {
        auto isVowel = [](char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; };
        unordered_map<int, int> mp{{0, 1}};
        int res = 0, sum = 0;
        for (auto& s : arr) {
            for (char c : s) sum += isVowel(c) ? 1 : -1;
            res += mp[sum]++;
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n*m) - Standard traversal
Auxiliary Space: 💾 O(n) - HashMap storage

✅ Why This Approach?

Modern C++ style with lambdas.
Clean and readable code.
Compiler optimization friendly.

📊 5️⃣ String Set-Based Vowel Check

💡 Algorithm Steps:

Use string set "aeiou" for vowel checking.
Utilize string's find method for character lookup.
Cleaner vowel identification logic.
Standard library optimized operations.

class Solution {
public:
    int countBalanced(vector<string>& arr) {
        string vowels = "aeiou";
        unordered_map<int, int> mp{{0, 1}};
        int res = 0, sum = 0;
        for (auto& s : arr) {
            for (char c : s) sum += (vowels.find(c) != string::npos) ? 1 : -1;
            res += mp[sum]++;
        }
        return res;
    }
};

📝 Complexity Analysis:

Time: ⏱️ O(n*m) - Linear with constant vowel check
Auxiliary Space: 💾 O(n) - HashMap storage

✅ Why This Approach?

Intuitive vowel checking method.
Standard library string operations.
Easy to understand and maintain.

🆚 🔍 Comparison of Approaches

🚀 Approach

⏱️ Time Complexity

💾 Space Complexity

✅ Pros

⚠️ Cons

🏷️ Prefix Sum Hash Map

🟢 O(n*m)

🟡 O(n)

🚀 Clean and intuitive

🔧 Hash map overhead

🔍 Bit Manipulation

🟢 O(n*m)

🟡 O(n)

📖 Faster vowel check

💾 Complex bit operations

📊 Array-Based

🟢 O(n*m)

🟢 O(1)

🎯 Better cache performance

🐌 Fixed memory allocation

🔄 Lambda Compact

🟢 O(n*m)

🟡 O(n)

⭐ Modern C++ style

🔧 Compiler-dependent optimization

🔤 String Set-Based

🟢 O(n*m)

🟡 O(n)

📝 Intuitive and readable

🔧 String find overhead

🏆 Best Choice Recommendation

🎯 Scenario

🎖️ Recommended Approach

🔥 Performance Rating

⚡ Maximum performance, competitive programming

🥇 Bit Manipulation

★★★★★

🔧 Production code, readability important

🥈 Prefix Sum Hash Map

★★★★☆

📊 Memory constrained environments

🥉 Array-Based

★★★★☆

🎯 Educational purposes, clear logic

🎖️ String Set-Based

★★★☆☆

📚 Modern C++ practices

🏅 Lambda Compact

★★★★☆

☕ Code (Java)

class Solution {
    public int countBalanced(String[] arr) {
        Map<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        int sum = 0, res = 0;
        for (String s : arr) {
            for (char c : s.toCharArray()) 
                sum += "aeiou".indexOf(c) >= 0 ? 1 : -1;
            res += mp.getOrDefault(sum, 0);
            mp.put(sum, mp.getOrDefault(sum, 0) + 1);
        }
        return res;
    }
}

🐍 Code (Python)

class Solution:
    def countBalanced(self, arr):
        mp, s, res = {0: 1}, 0, 0
        for string in arr:
            s += sum(1 if c in 'aeiou' else -1 for c in string)
            res += mp.get(s, 0)
            mp[s] = mp.get(s, 0) + 1
        return res

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

📍Visitor Count

PreviousAugust 2025 GFG SOLUTION Next02. Longest Subarray with Majority Greater than K

Last updated 6 months ago

hashtag🧩 Problem Description

hashtag📘 Examples

hashtagExample 1

hashtagExample 2

hashtagExample 3

hashtag🔒 Constraints

hashtag✅ My Approach

hashtagPrefix Sum + Hash Map

hashtag📝 Time and Auxiliary Space Complexity

hashtag🧑‍💻 Code (C++)

hashtag📊 2️⃣ Bit Manipulation Approach

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 3️⃣ Array-Based Frequency

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 4️⃣ Lambda-Based Compact

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag📊 5️⃣ String Set-Based Vowel Check

hashtag💡 Algorithm Steps:

hashtag📝 Complexity Analysis:

hashtag✅ Why This Approach?

hashtag🆚 🔍 Comparison of Approaches

hashtag🏆 Best Choice Recommendation

hashtag☕ Code (Java)

hashtag🐍 Code (Python)

hashtag🧠 Contribution and Support

hashtag📍Visitor Count

🧩 Problem Description

📘 Examples

Example 1

Example 2

Example 3

🔒 Constraints

✅ My Approach

Prefix Sum + Hash Map

📝 Time and Auxiliary Space Complexity

🧑‍💻 Code (C++)

📊 2️⃣ Bit Manipulation Approach

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 3️⃣ Array-Based Frequency

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 4️⃣ Lambda-Based Compact

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

📊 5️⃣ String Set-Based Vowel Check

💡 Algorithm Steps:

📝 Complexity Analysis:

✅ Why This Approach?

🆚 🔍 Comparison of Approaches

🏆 Best Choice Recommendation

☕ Code (Java)

🐍 Code (Python)

🧠 Contribution and Support

📍Visitor Count