Balancing Consonants and Vowels Ratio

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find substring where count of vowels equals count of consonants.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find substring where count of vowels equals count of consonants. Prefix count difference + hashmap.

Algorithm

1Track running (vowels - consonants). Use hashmap to find subarrays with difference = 0.

Common Pitfalls

• Reduce to "subarray with sum 0" via encoding vowels as +1 and consonants as -1. Hashmap of first occurrence.

Balancing Consonants and Vowels Ratio.java

Java

// Approach: Sliding window / prefix counts. Track counts of vowels and consonants.
// Find positions where their ratio meets the target.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public int countBalanced(String[] arr) {
        HashMap<Integer, Integer> map = new HashMap<>();

        map.put(0, 1);

        int sum = 0;
        int ans = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += countDiff(arr[i]);

            if (map.containsKey(sum))
                ans += map.get(sum);

            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return ans;
    }

    private boolean isVowel(char ch) {
        return "aeiuo".indexOf(ch) >= 0;
    }

    private int countDiff(String s) {
        int v = 0, c = 0;
        for (char ch : s.toCharArray()) {
            if (isVowel(ch))
                v++;
            else
                c++;
        }

        return v - c;
    }
}

Was this solution helpful?