Count Vowel Strings in Ranges

2559. Count Vowel Strings in Ranges

Difficulty: Medium

Topics: Array, String, Prefix Sum

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

Each query queries[i] = [l_i, r_i] asks us to find the number of strings present in the range l_i to r_i (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 that the vowel letters are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

• Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
• Output: [2,3,0]
• Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
  • The answer to the query [0,2] is 2 (strings "aba" and "ece").
  • to query [1,4] is 3 (strings "ece", "aa", "e").
  • to query [1,1] is 0.
  • We return [2,3,0].

Example 2:

• Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
• Output: [3,2,1]
• Explanation: Every string satisfies the conditions, so we return [3,2,1].

Constraints:

• 1 <= words.length <= 10⁵
• 1 <= words[i].length <= 40
• words[i] consists only of lowercase English letters.
• sum(words[i].length) <= 3 * 10⁵
• 1 <= queries.length <= 10⁵
• 0 <= l_i <= r_i < words.length

Hint:

1. Precompute the prefix sum of strings that start and end with vowels.
2. Use unordered_set to store vowels.
3. Check if the first and last characters of the string are present in the vowels set.
4. Subtract prefix sum for range [l-1, r] to find the number of strings starting and ending with vowels.

Solution:

We can follow these steps:

1. Check for Vowel Strings: Create a helper function to determine whether a string starts and ends with a vowel.
2. Precompute Prefix Sums: Use a prefix sum array to store the cumulative count of strings that start and end with vowels.
3. Answer Queries: Use the prefix sum array to efficiently calculate the number of such strings within the specified range for each query.

Let's implement this solution in PHP: 2559. Count Vowel Strings in Ranges

  
  
  Explanation:




isVowelString Function:


Checks if the first and last characters of the string are vowels.
Uses in_array to determine if the characters are in the predefined list of vowels.



Prefix Sum Array:



prefixSum[i] stores the cumulative count of vowel strings up to index i-1.
If the current word satisfies the condition, increment the count.



Query Resolution:


For a range [l, r], the count of vowel strings is prefixSum[r   1] - prefixSum[l].



Efficiency:


Constructing the prefix sum array takes O(n), where n is the number of words.
Resolving each query takes O(1), making the overall complexity O(n   q), where q is the number of queries.





  
  
  Edge Cases:



All strings start and end with vowels.
No strings start and end with vowels.
Single-element ranges in the queries.


This approach efficiently handles the constraints of the problem.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


LinkedIn
GitHub



          

            
        
The above is the detailed content of Count Vowel Strings in Ranges. For more information, please follow other related articles on the PHP Chinese website!