DSA Visualizations | Hello Interview

Count Vowels in Substrings

DESCRIPTION

Write a function to efficiently count vowels within specified substrings of a given string.

The substrings will be given to you a list queries of [left, right] pairs, which correspond to the substring word[left:right + 1] in Python.

The function should return a list of integers, where each integer represents the vowel count for the corresponding query. You can assume the input string will only contain lowercase letters.

Your function should be optimized to run efficiently for a large number of queries.

EXAMPLES

Input:


word = "prefixsum"
queries = [[0, 2], [1, 4], [3, 5]]

Output: [1, 2, 1]

Explanation:


word[0:3] -> "pre" contains 1 vowels
word[1:5]-> "refi" contains 2 vowels
word[3:6]-> "fix" contains 1 vowels

Run your code to see results here

Explanation

We can solve this question efficiently for a large number of queries of by using the Prefix Sum technique, with a slight modification.

Since our question is asking for the number of vowels in a substring, we can create a prefix sum array where prefix_sum[i] represents the number of vowels in the substring from index 0 to i - 1 (inclusive).

For example, for the string picture, our prefix_sum array would look like this:

Remember that in Python, to get the substring from index i to j (inclusive), you need to use word[i:j + 1].

As an example, let's say our word is picture and we want the substring from index 0 to 3 (inclusive). We would use word[0:4] to get the substring pict, which has 1 vowel. This would be stored as prefix_sum[4].

With the prefix_sum array, we can now calculate the nummber of vowels in any range using the formula prefix_sum[right + 1] - prefix_sum[left], where right and left are the indices of the substring as specified by each entry in the queries array.

The visual below shows how we can use the prefix_sum array to calculate the number of vowels in the substring picture when [left, right] = [1, 4]:

Using the prefix sum array count the vowels in pictu (word[1:5])

# of vowels in word[1:5] = prefix_sum[5] - prefix_sum[2]

So our solution has two parts:

1.) Create a prefix sum array prefix_sum where prefix_sum[i] stores the number of vowels in the substring word[0:i].

2.) Iterate over the queries array and calculate the number of vowels in the substring specified by each query using the formula prefix_sum[right + 1] - prefix_sum[left], and store each result that we return at the end.

class Solution:
    def vowelStrings(self, word, queries):
        vowels = set('aeiou')
        prefix_sum = [0] * (len(word) + 1)

        # Part 1: create the prefix sum array
        for i in range(1, len(word) + 1):
            is_vowel = word[i - 1] in vowels
            prefix_sum[i] = prefix_sum[i - 1] + (1 if is_vowel else 0)

        # Part 2: calculate the number of vowels in each query 
        result = []
        for left, right in queries:
            num_vowels = prefix_sum[right + 1] - prefix_sum[left]
            result.append(num_vowels)
        
        return result

Complexity Analysis

Time Complexity: O(N + Q), where N is the length of the word string and Q is the number of queries in the queries array. We iterate over the word string to create the prefix sum array, which takes O(N) time. Then, we iterate over the queries array to calculate the number of vowels in each query. Each iteration takes O(1) time, so the total time complexity is O(N + Q).

Space Complexity: O(N + Q), where N is the length of the word string. We use O(N) space to store the prefix sum array, and O(Q) space to store the results of the queries.

Next: Subarray Sum Equals K

Your account is free and you can post anonymously if you choose.

Loading comments...

Back to Home

Eliminating Pairs

Overview

Container With Most Water

3-Sum

Triangle Numbers

Pointers as Regions

Move Zeroes

Sort Colors

Trapping Rain Water

Variable-Length

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Fixed-Length

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Monotonic Stack

Overview

Daily Temperatures

Largest Rectangle in Histogram

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Introduction

Binary Trees

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs

Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Topological Sort

Overview

Course Schedule

Course Schedule II

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Overview

Implement Trie Methods

Prefix Matching

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Overview

Subarray Sum Equals K

Count Vowels in Substrings

DESCRIPTION

Write a function to efficiently count vowels within specified substrings of a given string.

The substrings will be given to you a list queries of [left, right] pairs, which correspond to the substring word[left:right + 1] in Python.

The function should return a list of integers, where each integer represents the vowel count for the corresponding query. You can assume the input string will only contain lowercase letters.

Your function should be optimized to run efficiently for a large number of queries.

EXAMPLES

Input:


word = "prefixsum"
queries = [[0, 2], [1, 4], [3, 5]]

Output: [1, 2, 1]

Explanation:


word[0:3] -> "pre" contains 1 vowels
word[1:5]-> "refi" contains 2 vowels
word[3:6]-> "fix" contains 1 vowels

Run your code to see results here

Explanation

We can solve this question efficiently for a large number of queries of by using the Prefix Sum technique, with a slight modification.

For example, for the string picture, our prefix_sum array would look like this:

Remember that in Python, to get the substring from index i to j (inclusive), you need to use word[i:j + 1].

The visual below shows how we can use the prefix_sum array to calculate the number of vowels in the substring picture when [left, right] = [1, 4]:

Using the prefix sum array count the vowels in pictu (word[1:5])

# of vowels in word[1:5] = prefix_sum[5] - prefix_sum[2]

So our solution has two parts:

1.) Create a prefix sum array prefix_sum where prefix_sum[i] stores the number of vowels in the substring word[0:i].

class Solution:
    def vowelStrings(self, word, queries):
        vowels = set('aeiou')
        prefix_sum = [0] * (len(word) + 1)

        # Part 1: create the prefix sum array
        for i in range(1, len(word) + 1):
            is_vowel = word[i - 1] in vowels
            prefix_sum[i] = prefix_sum[i - 1] + (1 if is_vowel else 0)

        # Part 2: calculate the number of vowels in each query 
        result = []
        for left, right in queries:
            num_vowels = prefix_sum[right + 1] - prefix_sum[left]
            result.append(num_vowels)
        
        return result

Complexity Analysis

Space Complexity: O(N + Q), where N is the length of the word string. We use O(N) space to store the prefix sum array, and O(Q) space to store the results of the queries.

Next: Subarray Sum Equals K

Your account is free and you can post anonymously if you choose.

Loading comments...

BlogBehavioral Interview Examples Interviewing for Experienced SWEs All Blog Posts

Compare UsCompare to Interviewing.io

LinksFAQ Schedule Mock Interviews Pricing Become a Coach Our Coaches Learn System Design Learn DSA

LegalTerms and Conditions Privacy Policy

Contactsupport@hellointerview.com7511 Greenwood Ave North
Unit #4238 Seattle, WA 98103