Plates between candles

Array String Binary Search Prefix Sum

47.3% acceptance

Feb 25, 2026

1353

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn plates_between_candles(s: String, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();

    // prefix_plates[i] = number of '*' in s[0..i]
    let mut prefix_plates = vec![0i32; n + 1];
    for i in 0..n {
      prefix_plates[i + 1] = prefix_plates[i] + if s[i] == b'*' { 1 } else { 0 };
    }

    // left_candle[i] = index of nearest candle at or to the left of i (-1 if none)
    let mut left_candle = vec![-1i32; n];
    for i in 0..n {
      if s[i] == b'|' {
        left_candle[i] = i as i32;
      } else if i > 0 && left_candle[i - 1] >= 0 {
        left_candle[i] = left_candle[i - 1];
      }
    }

    // right_candle[i] = index of nearest candle at or to the right of i (-1 if none)
    let mut right_candle = vec![-1i32; n];
    for i in (0..n).rev() {
      if s[i] == b'|' {
        right_candle[i] = i as i32;
      } else if i + 1 < n && right_candle[i + 1] >= 0 {
        right_candle[i] = right_candle[i + 1];
      }
    }

    queries.iter().map(|q| {
      let (l, r) = (q[0] as usize, q[1] as usize);
      let left = right_candle[l];
      let right = left_candle[r];
      if left < 0 || right < 0 || left >= right {
        0
      } else {
        prefix_plates[right as usize] - prefix_plates[left as usize]
      }
    }).collect()
  }
}