StringTransformation
SRM 777 · 2020-01-26 · by Witaliy
Problem Statement
You have a sequence of red, green, and blue balls.
The sequence is described by the
The only transformation allowed looks as follows: Let p,q,r,s be four consecutive balls. If balls q and r have the same color and at the same time balls p and s have different colors, you may remove the balls q and r.
Formally, you may choose an index i such that s[i+1] = s[i+2] and at the same time s[i] != s[i+3]. If you do, you may remove the characters at indices i+1 and i+2 from s.
Return "YES" (quotes for clarity) if there is a sequence of zero or more transformations that converts s into t. Otherwise, return "NO".
Constraints
- s and t will contain between 1 and 2,500 characters.
- s and t will consist only of characters R, G and B.
"RGGG" "RG" Returns: "YES"
As we have s[1] = s[2] and s[0] != s[3], we may remove the two middle characters of s to obtain t.
"RGRGRBRGRB" "RGRGRBRGRB" Returns: "YES"
If s = t, we do not have to do anything.
"R" "RRRRGBR" Returns: "NO"
As we can only remove balls, this transformation is clearly impossible.
"RGBRGGRRBGB" "RGBRBGB" Returns: "YES"
Two consecutive transformations are needed here.
"RR" "R" Returns: "NO"
Submissions are judged against all 154 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StringTransformation with a public method string getResult(string s, string t) · 154 test cases · 2 s / 256 MB per case