2559. Count Vowel Strings in Ranges

Description

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

Solutions

Solution 1: Preprocessing + Binary Search

We can preprocess all the indices of the strings that start and end with a vowel, and record them in order in the array \(nums\).

Next, we iterate through each query \((l, r)\), and use binary search to find the first index \(i\) in \(nums\) that is greater than or equal to \(l\), and the first index \(j\) that is greater than \(r\). Therefore, the answer to the current query is \(j - i\).

The time complexity is \(O(n + m \times \log n)\), and the space complexity is \(O(n)\). Where \(n\) and \(m\) are the lengths of the arrays \(words\) and \(queries\), respectively.

Python3JavaC++GoTypeScript

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = set("aeiou")
        nums = [i for i, w in enumerate(words) if w[0] in vowels and w[-1] in vowels]
        return [bisect_right(nums, r) - bisect_left(nums, l) for l, r in queries]

class Solution {
    private List<Integer> nums = new ArrayList<>();

    public int[] vowelStrings(String[] words, int[][] queries) {
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        for (int i = 0; i < words.length; ++i) {
            char a = words[i].charAt(0), b = words[i].charAt(words[i].length() - 1);
            if (vowels.contains(a) && vowels.contains(b)) {
                nums.add(i);
            }
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = search(r + 1) - search(l);
        }
        return ans;
    }

    private int search(int x) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums.get(mid) >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
        vector<int> nums;
        for (int i = 0; i < words.size(); ++i) {
            char a = words[i][0], b = words[i].back();
            if (vowels.count(a) && vowels.count(b)) {
                nums.push_back(i);
            }
        }
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            int cnt = upper_bound(nums.begin(), nums.end(), r) - lower_bound(nums.begin(), nums.end(), l);
            ans.push_back(cnt);
        }
        return ans;
    }
};

func vowelStrings(words []string, queries [][]int) []int {
    vowels := map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    nums := []int{}
    for i, w := range words {
        if vowels[w[0]] && vowels[w[len(w)-1]] {
            nums = append(nums, i)
        }
    }
    ans := make([]int, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]
        ans[i] = sort.SearchInts(nums, r+1) - sort.SearchInts(nums, l)
    }
    return ans
}

function vowelStrings(words: string[], queries: number[][]): number[] {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    const nums: number[] = [];
    for (let i = 0; i < words.length; ++i) {
        if (vowels.has(words[i][0]) && vowels.has(words[i][words[i].length - 1])) {
            nums.push(i);
        }
    }
    const search = (x: number): number => {
        let l = 0,
            r = nums.length;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    return queries.map(([l, r]) => search(r + 1) - search(l));
}

Solution 2: Prefix Sum

We can create a prefix sum array \(s\) of length \(n+1\), where \(s[i]\) represents the number of strings that start and end with a vowel in the first \(i\) strings of the array \(words\). Initially, \(s[0] = 0\).

Next, we iterate through the array \(words\). If the current string starts and ends with a vowel, then \(s[i+1] = s[i] + 1\), otherwise \(s[i+1] = s[i]\).

Finally, we iterate through each query \((l, r)\). Therefore, the answer to the current query is \(s[r+1] - s[l]\).

The time complexity is \(O(n + m)\), and the space complexity is \(O(n)\). Where \(n\) and \(m\) are the lengths of the arrays \(words\) and \(queries\), respectively.

Python3JavaC++GoTypeScriptJavaScript

class Solution:
    def vowelStrings(self, words: List[str], queries: List[List[int]]) -> List[int]:
        vowels = set("aeiou")
        s = list(
            accumulate(
                (int(w[0] in vowels and w[-1] in vowels) for w in words), initial=0
            )
        )
        return [s[r + 1] - s[l] for l, r in queries]

class Solution {
    public int[] vowelStrings(String[] words, int[][] queries) {
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        int n = words.length;
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            char a = words[i].charAt(0), b = words[i].charAt(words[i].length() - 1);
            s[i + 1] = s[i] + (vowels.contains(a) && vowels.contains(b) ? 1 : 0);
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = s[r + 1] - s[l];
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
        int n = words.size();
        int s[n + 1];
        s[0] = 0;
        for (int i = 0; i < n; ++i) {
            char a = words[i][0], b = words[i].back();
            s[i + 1] = s[i] + (vowels.count(a) && vowels.count(b));
        }
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            ans.push_back(s[r + 1] - s[l]);
        }
        return ans;
    }
};

func vowelStrings(words []string, queries [][]int) []int {
    vowels := map[byte]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    n := len(words)
    s := make([]int, n+1)
    for i, w := range words {
        x := 0
        if vowels[w[0]] && vowels[w[len(w)-1]] {
            x = 1
        }
        s[i+1] = s[i] + x
    }
    ans := make([]int, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]
        ans[i] = s[r+1] - s[l]
    }
    return ans
}

function vowelStrings(words: string[], queries: number[][]): number[] {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    const s = new Array(words.length + 1).fill(0);

    words.forEach((w, i) => {
        const x = +(vowels.has(w[0]) && vowels.has(w.at(-1)!));
        s[i + 1] = s[i] + x;
    });

    return queries.map(([l, r]) => s[r + 1] - s[l]);
}

function vowelStrings(words, queries) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    const s = new Array(words.length + 1).fill(0);

    words.forEach((w, i) => {
        const x = +(vowels.has(w[0]) && vowels.has(w.at(-1)));
        s[i + 1] = s[i] + x;
    });

    return queries.map(([l, r]) => s[r + 1] - s[l]);
}

Comments