LineOff
TCO18 Fun 1B · 2018-04-20 · by Nickolas
Problem Statement
You are given a set of colored points on a straight line.
You play a game with these points. The game is a sequence of moves. In each move you have to erase two points that are adjacent and share the same color. (Two points are adjacent if there is no other point between them. Distances don't matter.)
You are given the
Constraints
- points will contain between 1 and 50 characters, inclusive.
- Each character in points will be a lowercase English letter ('a'-'z').
"abba" Returns: 2
The only valid first move is to erase the two points of color 'b'. After that move the points of color 'a' are now adjacent and they can be removed in our second move.
"zwwwzffw" Returns: 2
You can remove two 'w' points and two 'f' points with your first two moves. After that the remaining points on the line will be arranged as follows: "zwzw". In this situation you don't have any adjacent points that share the same color, so there are no more moves.
"rrrrrrr" Returns: 3
With an odd number of points, at least one of them will have no pair.
"dfghj" Returns: 0
All colors are different so no points can be removed.
"wasitacarooracatisaw" Returns: 10
"abcdefghijklmnopqrstuvxyzzyxvutsrqponmlkjihgfedcba" Returns: 25
max test specific move order
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" Returns: 25
max test any order
"k" Returns: 0
min test
Submissions are judged against all 37 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LineOff with a public method int movesToDo(string points) · 37 test cases · 2 s / 256 MB per case