Candy Crush Reduction
MediumLinked List · Oracle
A one-row candy board is given as a string s of lowercase letters, one letter per candy. A run is a maximal block of equal adjacent letters (in "abbbca" the runs are a, bbb, c, a).
The board resolves in passes:
- In each pass, every run of length 2 or more is crushed at the same time. A run is always crushed whole; you cannot crush just part of it, and you have no choice about what to crush.
- The remaining candies then slide together. This can put equal letters next to each other that were not neighbours before; those new runs are crushed in the next pass, not the current one.
- Passes repeat until a pass finds no run of length 2 or more.
Return the number of candies left when the board stops changing.
s can be long, and a board can need many passes (each pass might remove only a couple of candies), so re-scanning the whole string on every pass may be too slow.
Example 1
- Input:
- s = "abccbaa"
- Output:
- 1
- Explanation
- Pass 1 crushes
ccandaatogether, leavingabb. Pass 2 crushesbb, leavinga. The finalanever meets the crushedaa, because that run was already gone in pass 1, so 1 candy remains.
Example 2
- Input:
- s = "aabbbac"
- Output:
- 2
- Explanation
- Pass 1 crushes
aaandbbbat the same time, leavingac, which has no run of length 2. Theaacannot be held back to join the latera, so 2 candies remain.
Example 3
- Input:
- s = "abcddcba"
- Output:
- 0
- Explanation
- Each pass removes only the middle pair:
dd, thencc, thenbb, thenaa, leaving an empty board with 0 candies.
Constraints
- 0 ≤ s.length ≤ 105
sconsists of lowercase English letters.