Count Vowel Strings in Ranges - Practice Coding Problems

Count Vowel Strings in Ranges - Problem

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [li, ri] asks us to find the number of strings present at the indices ranging from li to ri (both inclusive) of words that start and end with a vowel.

Return an array ans of size queries.length, where ans[i] is the answer to the i^th query.

Note: The vowel letters are 'a', 'e', 'i', 'o', and 'u'.

Input & Output

Example 1 — Basic Case

$ Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4]]

› Output: [2,3]

💡 Note: Query [0,2]: "aba"✗, "bcb"✓, "ece"✓ → count = 2. Query [1,4]: "bcb"✓, "ece"✓, "aa"✗, "e"✓ → count = 3.

Example 2 — Single Elements

$ Input: words = ["a","e","i"], queries = [[0,2],[0,1]]

› Output: [3,2]

💡 Note: All single vowel strings qualify. Query [0,2]: all 3 strings qualify. Query [0,1]: first 2 strings qualify.

Example 3 — No Valid Strings

$ Input: words = ["hello","world","code"], queries = [[0,2]]

› Output: [0]

💡 Note: "hello" starts with 'h', "world" starts with 'w', "code" ends with 'e' but starts with 'c'. None qualify.

Constraints

1 ≤ words.length ≤ 10⁵
1 ≤ words[i].length ≤ 40
words[i] consists only of lowercase English letters
sum(queries.length) ≤ 3 × 10⁵
0 ≤ queries[i][0] ≤ queries[i][1] < words.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and query ranges

Process

Identify words starting/ending with vowels

Output

Count of valid words in each query range

Key Takeaway

🎯 Key Insight: Use prefix sums to transform multiple range queries into constant-time lookups

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use prefix sums for efficient range queries. After identifying words that start and end with vowels, build a cumulative count array. This allows answering any query [l,r] in O(1) time using the formula prefix[r+1] - prefix[l]. Best approach is prefix sum with Time: O(N + Q), Space: O(N).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(N + Q)	O(N)	Pre-compute cumulative counts for instant range queries
Brute Force	O(Q × N × M)	O(1)	Check each word in every query range individually

Prefix Sum Optimization — Algorithm Steps

Step 1: Create boolean array marking words that start/end with vowels
Step 2: Build prefix sum array with cumulative counts
Step 3: Answer queries using prefix[r+1] - prefix[l]

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark Valid Words

Identify words starting and ending with vowels

Build Prefix Sum

Create cumulative count array

Answer Queries

Use prefix[r+1] - prefix[l] formula

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
           c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}

bool startsEndsVowel(char* word) {
    int len = strlen(word);
    return len > 0 && isVowel(word[0]) && isVowel(word[len-1]);
}

int* solution(char** words, int wordsSize, int** queries, int queriesSize, int* returnSize) {
    int* prefix = (int*)malloc((wordsSize + 1) * sizeof(int));
    prefix[0] = 0;
    
    // Build prefix sum array
    for (int i = 0; i < wordsSize; i++) {
        prefix[i + 1] = prefix[i] + (startsEndsVowel(words[i]) ? 1 : 0);
    }
    
    // Answer queries
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int l = queries[i][0], r = queries[i][1];
        result[i] = prefix[r + 1] - prefix[l];
    }
    
    free(prefix);
    return result;
}

int main() {
    // Parse input and call solution
    // Print result in [1,2,3] format
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(N + Q)

O(N) to build prefix sum, O(1) per query for Q queries

✓ Linear Growth

Space Complexity

O(N)

Prefix sum array stores N+1 cumulative counts

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler