Chain of gems
- O(n²) · Very hard
- Full plan
- Python
- JavaScript
- strings
- loops
- indexes
Problem
It is two in the morning and Renata has one shot left to clear level 40 of her gem game; before she takes it, she wants to know how the strip will look once the chain of explosions is over.
You get gems, the strip as it would be with her gem already placed: a text of uppercase letters, one letter per gem, giving its color (it may be empty). A group is 3 or more equal letters in a row, counted whole: in "CAAAAB" the group is "AAAA".
While there is any group, remove the one that starts furthest to the left, join what is left and check again from the beginning.
Return the final text; if everything exploded, return "".
With "ABBBAAC": "BBB" explodes and "AAAC" is left; now the As came together and "AAA" explodes, leaving "C", which has no groups: you return "C". Order matters: in "BAAABBCCCB" first "AAA" explodes, then "BBB" and then "CCC", and you return "B". With "AABB" there are no groups and you return "AABB" as it is.
Examples
The example
"ABBBAAC" → "C"
The leftmost one first
"BAAABBCCCB" → "B"
No groups
"AABB" → "AABB"
A group of four
"AAAA" → ""
The explosion brings others together
"AABBBAC" → "C"
Two left, no explosion
"ABBBAC" → "AAC"
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def final_strip(gems):
passJavaScript
function finalStrip(gems) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.