StringTransformation | Topcoder Archive

Problem Statement

You have a sequence of red, green, and blue balls. The sequence is described by the String s: red balls are denoted 'R', green ones 'G' and blue ones 'B'. 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".

Definition

Class:: StringTransformation
Method:: getResult
Parameters:: String, String
Returns:: String
Method signature:: String getResult(String s, String t)
(be sure your method is public)

Constraints

s and t will contain between 1 and 2,500 characters.
s and t will consist only of characters R, G and B.

Examples

```
"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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.