Plates Between Candles

medium array string binary search prefix sum

Problem

Given a string s of '*' (plates) and '|' (candles) and queries [L, R], return for each query the number of plates between two candles inside s[L..R].

Inputs = "**|**|***|", queries = [[2,5],[5,9]]

Output[2, 3]

First query: 2 plates between candles at indices 2 and 5.

s (* and |)

def plates_between_candles(s, queries):
    n = len(s)
    prefix = [0] * (n + 1)
    nxt = [n] * n
    prv = [-1] * n
    last = -1
    for i, ch in enumerate(s):
        prefix[i + 1] = prefix[i] + (1 if ch == '*' else 0)
        if ch == '|':
            last = i
        prv[i] = last
    last = n
    for i in range(n - 1, -1, -1):
        if s[i] == '|':
            last = i
        nxt[i] = last
    ans = []
    for L, R in queries:
        l = nxt[L] if L < n else n
        r = prv[R] if R >= 0 else -1
        ans.append(prefix[r + 1] - prefix[l] if l < r else 0)
    return ans

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

class Solution {
    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int[] prefix = new int[n + 1];
        int[] nxt = new int[n];
        int[] prv = new int[n];
        int last = -1;
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (s.charAt(i) == '*' ? 1 : 0);
            if (s.charAt(i) == '|') last = i;
            prv[i] = last;
        }
        last = n;
        for (int i = n - 1; i >= 0; i--) {
            if (s.charAt(i) == '|') last = i;
            nxt[i] = last;
        }
        int[] ans = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int L = queries[q][0], R = queries[q][1];
            int l = nxt[L], r = prv[R];
            ans[q] = l < r ? prefix[r + 1] - prefix[l] : 0;
        }
        return ans;
    }
}

vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
    int n = s.size();
    vector<int> prefix(n + 1, 0), nxt(n, n), prv(n, -1);
    int last = -1;
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + (s[i] == '*' ? 1 : 0);
        if (s[i] == '|') last = i;
        prv[i] = last;
    }
    last = n;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '|') last = i;
        nxt[i] = last;
    }
    vector<int> ans;
    for (auto& q : queries) {
        int l = nxt[q[0]], r = prv[q[1]];
        ans.push_back(l < r ? prefix[r + 1] - prefix[l] : 0);
    }
    return ans;
}

Explanation

For each query we want the plates (*) that lie between two candles (|) inside a range. Doing this by scanning the range each time would be slow when there are many queries, so we precompute three helper arrays and answer every query in constant time.

prefix[i] is a prefix count of plates in the first i characters, so the number of plates in any range is one subtraction. prv[i] is the nearest candle at or before index i, and nxt[i] is the nearest candle at or after i.

For a query [L, R], the leftmost usable candle is l = nxt[L] and the rightmost is r = prv[R]. If l < r there is a valid enclosed stretch, and the plate count is prefix[r + 1] - prefix[l]. Otherwise the answer is 0.

Example: s = "**|**|***|", query [2, 5]. The first candle at or after index 2 is index 2, the last at or before 5 is index 5, and between them sit 2 plates — the answer for that query.

Time: O(n + q) Space: O(n)