Problem

There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters '*' and '|' only, where a '*' represents a plate and a '|' represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [lefti, righti] denotes the substring s[lefti...righti] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

  • For example, s = "||**||**|*", and a query [3, 8] denotes the substring "*||**_**_** |". The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

Return an integer array answer where answer[i] is the answer to the ith query.

Examples

Example 1

1
2
3
4
5
6
7
8


![ex-1](https://assets.leetcode.com/uploads/2021/10/04/ex-1.png)

Input: s = "**|**|***|", queries = [[2,5],[5,9]]
Output: [2,3]
Explanation:
- queries[0] has two plates between candles.
- queries[1] has three plates between candles.

Example 2

1
2
3
4
5
6
7
8


![ex-2](https://assets.leetcode.com/uploads/2021/10/04/ex-2.png)

Input: s = "***|**|*****|**||**|*", queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]
Output: [9,0,0,0,0]
Explanation:
- queries[0] has nine plates between candles.
- The other queries have zero plates between candles.

Constraints

  • 3 <= s.length <= 10^5
  • s consists of '*' and '|' characters.
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 0 <= lefti <= righti < s.length

Solution

Intuition

For each query, we need to efficiently count the number of plates (’*’) that are between two candles (’|’) within the substring. Since both s and queries can be large, a brute-force approach is too slow. We can use prefix sums and precompute the nearest candle to the left and right for each position to answer each query in O(1) time after O(n) preprocessing.

Approach

  1. Precompute prefix sums of plates up to each index.
  2. For each position, precompute the index of the nearest candle to the left and to the right.
  3. For each query [l, r]:
    • Find the first candle at or after l (left_candle).
    • Find the last candle at or before r (right_candle).
    • If left_candle < right_candle, the answer is prefix_sum[right_candle] - prefix_sum[left_candle]. Otherwise, answer is 0.

Code

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

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        int n = s.size();
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; ++i)
            prefix[i + 1] = prefix[i] + (s[i] == '*' ? 1 : 0);
        vector<int> left(n, -1), right(n, n);
        for (int i = 0, last = -1; i < n; ++i) {
            if (s[i] == '|') last = i;
            left[i] = last;
        }
        for (int i = n - 1, last = n; i >= 0; --i) {
            if (s[i] == '|') last = i;
            right[i] = last;
        }
        vector<int> res;
        for (auto& q : queries) {
            int l = right[q[0]], r = left[q[1]];
            if (l < r)
                res.push_back(prefix[r] - prefix[l]);
            else
                res.push_back(0);
        }
        return res;
    }
};
Go
 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
34
35
36

func platesBetweenCandles(s string, queries [][]int) []int {
    n := len(s)
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i]
        if s[i] == '*' {
            prefix[i+1]++
        }
    }
    left := make([]int, n)
    right := make([]int, n)
    last := -1
    for i := 0; i < n; i++ {
        if s[i] == '|' {
            last = i
        }
        left[i] = last
    }
    last = n
    for i := n - 1; i >= 0; i-- {
        if s[i] == '|' {
            last = i
        }
        right[i] = last
    }
    res := make([]int, len(queries))
    for i, q := range queries {
        l, r := right[q[0]], left[q[1]]
        if l < r {
            res[i] = prefix[r] - prefix[l]
        } else {
            res[i] = 0
        }
    }
    return res
}
Java
 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

import java.util.*;
class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++)
            prefix[i + 1] = prefix[i] + (s.charAt(i) == '*' ? 1 : 0);
        int[] left = new int[n], right = new int[n];
        int last = -1;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '|') last = i;
            left[i] = last;
        }
        last = n;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '|') last = i;
            right[i] = last;
        }
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = right[queries[i][0]], r = left[queries[i][1]];
            if (l < r)
                res[i] = prefix[r] - prefix[l];
            else
                res[i] = 0;
        }
        return res;
    }
}
Kotlin
 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

class Solution {
    fun platesBetweenCandles(s: String, queries: Array<IntArray>): IntArray {
        val n = s.length
        val prefix = IntArray(n + 1)
        for (i in 0 until n)
            prefix[i + 1] = prefix[i] + if (s[i] == '*') 1 else 0
        val left = IntArray(n)
        val right = IntArray(n)
        var last = -1
        for (i in 0 until n) {
            if (s[i] == '|') last = i
            left[i] = last
        }
        last = n
        for (i in n - 1 downTo 0) {
            if (s[i] == '|') last = i
            right[i] = last
        }
        return queries.map {
            val l = right[it[0]]
            val r = left[it[1]]
            if (l < r) prefix[r] - prefix[l] else 0
        }.toIntArray()
    }
}
Python
 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

class Solution:
    def platesBetweenCandles(self, s: str, queries: list[list[int]]) -> list[int]:
        n = len(s)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + (s[i] == '*')
        left = [-1] * n
        right = [n] * n
        last = -1
        for i in range(n):
            if s[i] == '|':
                last = i
            left[i] = last
        last = n
        for i in range(n - 1, -1, -1):
            if s[i] == '|':
                last = i
            right[i] = last
        res = []
        for l, r in queries:
            l_candle = right[l]
            r_candle = left[r]
            if l_candle < r_candle:
                res.append(prefix[r_candle] - prefix[l_candle])
            else:
                res.append(0)
        return res
Rust
 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

impl Solution {
    pub fn plates_between_candles(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = s.len();
        let s = s.as_bytes();
        let mut prefix = vec![0; n + 1];
        for i in 0..n {
            prefix[i + 1] = prefix[i] + if s[i] == b'*' { 1 } else { 0 };
        }
        let mut left = vec![-1; n];
        let mut right = vec![n as i32; n];
        let mut last = -1;
        for i in 0..n {
            if s[i] == b'|' { last = i as i32; }
            left[i] = last;
        }
        last = n as i32;
        for i in (0..n).rev() {
            if s[i] == b'|' { last = i as i32; }
            right[i] = last;
        }
        queries.iter().map(|q| {
            let l = right[q[0] as usize];
            let r = left[q[1] as usize];
            if l < r {
                prefix[r as usize] - prefix[l as usize]
            } else { 0 }
        }).collect()
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function platesBetweenCandles(s: string, queries: number[][]): number[] {
    const n = s.length;
    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++)
        prefix[i + 1] = prefix[i] + (s[i] === '*' ? 1 : 0);
    const left = new Array(n).fill(-1);
    const right = new Array(n).fill(n);
    let last = -1;
    for (let i = 0; i < n; i++) {
        if (s[i] === '|') last = i;
        left[i] = last;
    }
    last = n;
    for (let i = n - 1; i >= 0; i--) {
        if (s[i] === '|') last = i;
        right[i] = last;
    }
    return queries.map(([l, r]) => {
        const lCandle = right[l], rCandle = left[r];
        return lCandle < rCandle ? prefix[rCandle] - prefix[lCandle] : 0;
    });
}

Complexity

  • ⏰ Time complexity: O(n + q), where n is the length of s and q is the number of queries.
  • 🧺 Space complexity: O(n) for prefix sums and nearest candle arrays.