2559. 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] = [li, ri] asks us to find the number of strings present in the range 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 ith 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 <= 105
• 1 <= words[i].length <= 40
• words[i] consists only of lowercase English letters.
• sum(words[i].length) <= 3 * 105
• 1 <= queries.length <= 105
• 0 <= li <= ri < 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

<?php
/**
 * @param String[] $words
 * @param Integer[][] $queries
 * @return Integer[]
 */
function vowelStrings($words, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a string starts and ends with a vowel
 *
 * @param $word
 * @return bool
 */
function isVowelString($word) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$words1 = ["aba", "bcb", "ece", "aa", "e"];
$queries1 = [[0, 2], [1, 4], [1, 1]];
print_r(countVowelStringsInRanges($words1, $queries1)); // Output: [2, 3, 0]

// Example 2
$words2 = ["a", "e", "i"];
$queries2 = [[0, 2], [0, 1], [2, 2]];
print_r(countVowelStringsInRanges($words2, $queries2)); // Output: [3, 2, 1]
?>

Explanation:

1. 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.

2. 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.

3. Query Resolution:

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

4. 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