Optimizing Vowel Count Queries In O(n) Time Complexity
Calculate prefix[] in O(n) and get vowel counts in O(k). Solution: iterate words, update prefix[], then calculate result for each query using prefix[]. Vowel check: a,e,i,o,u.
Problem
TC: O(n) for calculating the prefix[] and O(k) for getting all the counts of the vowels in the given ranges
class Solution {
public int[] vowelStrings(String[] words, int[][] queries) {
int result[] = new int[queries.length];
int prefix[] = new int[words.length];
int currentCount =0;
for(int i=0;i<words.length;i++){
String s= words[i];
currentCount+=check(s.charAt(0)) && check(s.charAt(s.length()-1)) ? 1:0;
prefix[i] = currentCount;
}
for(int i = 0;i<queries.length;i++){
int left = qu...