Problem Description

You have a string s that represents a long table with plates and candles arranged on it. The string consists only of:

• '*' representing a plate
• '|' representing a candle

Given a list of queries where each query [left, right] specifies a substring s[left...right] (inclusive), you need to count how many plates are between candles within that substring.

A plate is considered "between candles" if:

• There is at least one candle to its left in the substring, AND
• There is at least one candle to its right in the substring

Example: For s = "||**||**|*" and query [3, 8]:

• The substring is "*||**|" (from index 3 to 8)
• Looking at the plates in this substring:
  • The first * at index 3 has no candle to its left in the substring
  • The two * at indices 6-7 have candles on both sides (at indices 4-5 to the left and index 8 to the right)
  • So the answer is 2

The solution uses preprocessing to efficiently handle multiple queries:

1. Prefix sum array (presum): Counts the total number of plates from the start up to each position
2. Left array (left): For each position, stores the index of the nearest candle to the left (or -1 if none exists)
3. Right array (right): For each position, stores the index of the nearest candle to the right (or -1 if none exists)

For each query [l, r]:

• Find the leftmost candle in the range using right[l] (first candle at or after position l)
• Find the rightmost candle in the range using left[r] (last candle at or before position r)
• If both candles exist and the leftmost is before the rightmost, count plates between them using the prefix sum

Return an array where each element is the answer to the corresponding query.

Intuition

The key insight is that plates are only counted if they're between two candles within the query range. This means we need to find the leftmost and rightmost candles in any given range, then count the plates between them.

Consider what happens when we get a query [l, r]:

• Not all positions in this range matter - only the candles do
• Specifically, we care about the first candle from position l onwards and the last candle up to position r
• All plates between these two candles (if they exist) should be counted

The naive approach would be to scan each query range to find candles and count plates, but with multiple queries, this becomes inefficient. Instead, we can preprocess the string once to answer any query in constant time.

The preprocessing strategy emerges from these observations:

1. Finding boundary candles quickly: For any starting position, we want to know "where's the next candle?" and "where's the previous candle?". This leads us to create two arrays:

   • right[i]: the position of the nearest candle at or after index i
   • left[i]: the position of the nearest candle at or before index i

2. Counting plates efficiently: Once we know the two boundary candles, we need to count plates between them. Instead of iterating through the range, we can use a prefix sum array where presum[i] stores the total number of plates from the start up to position i-1. Then the number of plates between positions i and j is simply presum[j] - presum[i+1].

The beauty of this approach is that after O(n) preprocessing, each query can be answered in O(1) time:

• Use right[l] to find the leftmost candle in range
• Use left[r] to find the rightmost candle in range
• Use prefix sums to count plates between these candles

This transforms a potentially O(q * n) problem (where q is the number of queries) into an O(n + q) solution.

Learn more about Binary Search and Prefix Sum patterns.

Solution Approach

The implementation consists of three preprocessing steps followed by query processing:

Step 1: Build Prefix Sum Array

presum = [0] * (n + 1)
for i, c in enumerate(s):
    presum[i + 1] = presum[i] + (c == '*')

We create a prefix sum array where presum[i+1] stores the count of plates from index 0 to i. The expression (c == '*') evaluates to 1 if the character is a plate, 0 otherwise. This allows us to calculate the number of plates in any range [i, j] as presum[j+1] - presum[i].

Step 2: Build Left Array (Nearest Candle to the Left)

left = [0] * n
l = -1
for i, c in enumerate(s):
    if c == '|':
        l = i
    left[i] = l

We traverse the string from left to right. Variable l keeps track of the most recent candle position. For each position i, left[i] stores the index of the nearest candle at or before position i. If no candle exists to the left, it stores -1.

Step 3: Build Right Array (Nearest Candle to the Right)

right = [0] * n
r = -1
for i in range(n - 1, -1, -1):
    if s[i] == '|':
        r = i
    right[i] = r

Similar to the left array, but we traverse from right to left. For each position i, right[i] stores the index of the nearest candle at or after position i. If no candle exists to the right, it stores -1.

Step 4: Process Queries

ans = [0] * len(queries)
for k, (l, r) in enumerate(queries):
    i, j = right[l], left[r]
    if i >= 0 and j >= 0 and i < j:
        ans[k] = presum[j] - presum[i + 1]

For each query [l, r]:

• i = right[l]: Find the leftmost candle in the range (first candle at or after position l)
• j = left[r]: Find the rightmost candle in the range (last candle at or before position r)
• Check if both candles exist (i >= 0 and j >= 0) and the leftmost is before the rightmost (i < j)
• If valid, count plates between positions i and j using the formula: presum[j] - presum[i + 1]
  • We use i + 1 because we want to exclude position i (which is a candle) and start counting from i + 1
  • We use presum[j] which gives us the count up to position j - 1, effectively excluding the candle at position j

Time Complexity: O(n + q) where n is the length of string and q is the number of queries Space Complexity: O(n) for the three auxiliary arrays

Example Walkthrough

Let's walk through a small example with s = "**|**|*" and queries [[0, 6], [2, 5]].

Step 1: Build Prefix Sum Array We count plates (asterisks) cumulatively:

• Position 0: '*' → count = 1
• Position 1: '*' → count = 2
• Position 2: '|' → count = 2 (no change, it's a candle)
• Position 3: '*' → count = 3
• Position 4: '*' → count = 4
• Position 5: '|' → count = 4 (no change, it's a candle)
• Position 6: '*' → count = 5

presum = [0, 1, 2, 2, 3, 4, 4, 5]

Step 2: Build Left Array For each position, find the nearest candle to the left (or at that position):

• Positions 0-1: No candle to the left → -1
• Position 2: Candle at position 2 → 2
• Positions 3-4: Last candle was at position 2 → 2
• Position 5: Candle at position 5 → 5
• Position 6: Last candle was at position 5 → 5

left = [-1, -1, 2, 2, 2, 5, 5]

Step 3: Build Right Array For each position, find the nearest candle to the right (or at that position):

• Positions 0-1: Next candle is at position 2 → 2
• Position 2: Candle at position 2 → 2
• Positions 3-4: Next candle is at position 5 → 5
• Position 5: Candle at position 5 → 5
• Position 6: No candle to the right → -1

right = [2, 2, 2, 5, 5, 5, -1]

Step 4: Process Queries

Query 1: [0, 6]

• Find leftmost candle: right[0] = 2 (candle at position 2)
• Find rightmost candle: left[6] = 5 (candle at position 5)
• Both candles exist and 2 < 5 ✓
• Count plates between positions 2 and 5: presum[5] - presum[2+1] = 4 - 2 = 2
• The 2 plates are at positions 3 and 4, which are indeed between the candles

Query 2: [2, 5]

• Find leftmost candle: right[2] = 2 (candle at position 2)
• Find rightmost candle: left[5] = 5 (candle at position 5)
• Both candles exist and 2 < 5 ✓
• Count plates between positions 2 and 5: presum[5] - presum[2+1] = 4 - 2 = 2
• Same result as Query 1 since the candle boundaries are identical

Result: [2, 2]

The algorithm efficiently identifies that only the plates at positions 3 and 4 are between candles for both queries, giving us the correct answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + q) where n is the length of string s and q is the number of queries.

• Building the prefix sum array takes O(n) time with a single pass through the string
• Building the left array (nearest candle to the left) takes O(n) time with a single forward pass
• Building the right array (nearest candle to the right) takes O(n) time with a single backward pass
• Processing each query takes O(1) time since we're just doing array lookups and arithmetic operations
• Processing all q queries takes O(q) time
• Total: O(n) + O(n) + O(n) + O(q) = O(n + q)

Space Complexity: O(n) where n is the length of string s.

• The presum array uses O(n + 1) = O(n) space
• The left array uses O(n) space
• The right array uses O(n) space
• The ans array uses O(q) space for output (typically not counted in auxiliary space)
• Variables l, r, i, j, k use O(1) space
• Total auxiliary space: O(n) + O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Prefix Sum Calculation

Pitfall: A common mistake is incorrectly calculating the number of plates between two candles using the prefix sum array. Developers often confuse the indices and use formulas like:

• prefix_sum[right_candle + 1] - prefix_sum[left_candle] (incorrect)
• prefix_sum[right_candle] - prefix_sum[left_candle] (incorrect)

Why it happens: The confusion arises from the fact that prefix_sum[i] contains the count of plates from index 0 to i-1 (exclusive of i). When counting plates between two candles at positions left_candle and right_candle, we need to exclude both candle positions.

Correct approach:

# We want plates from (left_candle + 1) to (right_candle - 1) inclusive
plates_between = prefix_sum[right_candle] - prefix_sum[left_candle + 1]

2. Not Handling Edge Cases with No Candles

Pitfall: Forgetting to check if valid candles exist before calculating the plate count, leading to:

• Array index out of bounds when accessing prefix_sum[-1]
• Incorrect results when left_candle or right_candle is -1

Solution: Always validate that both candles exist and form a valid range:

if left_candle >= 0 and right_candle >= 0 and left_candle < right_candle:
    result[query_idx] = prefix_sum[right_candle] - prefix_sum[left_candle + 1]
else:
    result[query_idx] = 0  # No valid candles or no space between them

3. Confusing "Nearest" Candle Logic

Pitfall: Mixing up the direction of search for nearest candles:

• Using nearest_left_candle[left] instead of nearest_right_candle[left] for finding the leftmost candle in the query range
• Using nearest_right_candle[right] instead of nearest_left_candle[right] for finding the rightmost candle in the query range

Why it matters:

• For the left boundary of a query, we need the first candle at or after that position (search right)
• For the right boundary of a query, we need the last candle at or before that position (search left)

Correct mapping:

# For query [left, right]:
left_candle = nearest_right_candle[left]  # First candle >= left
right_candle = nearest_left_candle[right]  # Last candle <= right

4. Incorrect Prefix Sum Array Size

Pitfall: Creating the prefix sum array with size n instead of n + 1, causing index errors when accessing prefix_sum[n].

Solution: Always create prefix sum with size n + 1 where prefix_sum[0] = 0:

prefix_sum = [0] * (n + 1)  # Not [0] * n

5. Not Considering Adjacent Candles

Pitfall: Forgetting that when left_candle and right_candle are adjacent (differ by 1), there are no plates between them, but the condition left_candle < right_candle still passes.

Why it's not a problem in this solution: The prefix sum calculation naturally handles this case correctly: prefix_sum[right_candle] - prefix_sum[left_candle + 1] will return 0 when the candles are adjacent, as there are no plates between positions left_candle + 1 and right_candle - 1 when these positions don't exist.