Connection Status:
Competition Arena > StringTransformationEasy

StringTransformationEasy

SRM 777 · 2020-01-26 · by Witaliy

SRM 777 · 2020-01-26 · by Witaliy · Brute Force
Class Name: StringTransformationEasy
Return Type: String
Method Name: getResult
Arg Types: (string, string)
Problem Statement

Problem Statement

You have a sequence of red and green balls. The sequence is described by the String s: red balls are denoted 'R' and green ones 'G'. You would like to transform s into the target String t.

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 and G.
Examples
0)
"RRRRGGG"
"RRG"
Returns: "YES"
1)
"RRR"
"RRR"
Returns: "YES"
2)
"RRRGGRRRRGGG"
"RGGRRRRG"
Returns: "YES"
3)
"RRGG"
"RRGGGG"
Returns: "NO"
4)
"GGGG"
"GG"
Returns: "NO"

Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StringTransformationEasy with a public method string getResult(string s, string t) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous