Balancing Consonants and Vowels Ratio

JavaView on GFG

Time: O(n)

Space: O(1)

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?