Items In Containers
MediumPrefix Sum · Amazon
A shelf is described by a string s made of '*' (an item) and '|' (a compartment wall).
Each query [left, right] uses 1-indexed, inclusive positions and looks at the substring s[left..right] on its own, ignoring everything outside it. Within that substring, an item counts if there is at least one wall to its left and at least one wall to its right, both inside the substring. In other words, count the items lying between the first and last wall of the substring.
Return the counts for all queries, in query order.
Example 1
- Input:
- s = '*|*|**|*|', queries = [[1, 9], [3, 8], [2, 4]]
- Output:
- [4, 2, 1]
- Explanation
- Over the whole string the first wall is at position 2 and the last at 9, enclosing the items at 3, 5, 6 and 8. In
[3, 8]the walls inside are at 4 and 7, enclosing items 5 and 6; the items at 3 and 8 are outside them. In[2, 4]the walls at 2 and 4 enclose one item.
Example 2
- Input:
- s = '|*|', queries = [[1, 2], [1, 3]]
- Output:
- [0, 1]
- Explanation
- Positions 1-2 contain only one wall, so the item is not closed in. Positions 1-3 have walls on both sides of it.
Constraints
1 <= s.length <= 10^5scontains only'*'and'|'1 <= queries.length <= 10^51 <= left <= right <= s.length