Skip to content

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

Solutions

Thinking

Each query asks how many words in a range start and end with a vowel. Testing every word per query is too slow at \(n,q\le 10^5\).

Collect the qualifying indices in order. A query becomes a count of indices inside \([l,r]\), i.e. the difference of two binary searches.

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.

1
2
3
4
5
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

Thinking

Solution 1 still costs a logarithm per query. A \(0/1\) prefix sum of the vowel-string indicator answers each range as \(s[r+1]-s[l]\) in constant time.

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.

1
2
3
4
5
6
7
8
9
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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