FastPrepFastPrep
Problem Brief

Transform String

OA

A string S consisting of the letters A, B, C and D is given. The string can be transformed either by removing a letter A together with an adjacent letter B, or by removing a letter C together with an adjacent letter D.

Write a function:

string solution(string &S);

that, given a string S consisting of N characters, returns any string that:

  • can be obtained from S by repeatedly applying the described transformation, and
  • cannot be further transformed.

If at some point there is more than one possible way to transform the string, any of the valid transformations may be chosen.

Write an efficient algorithm for the following assumptions:

  • the length of string S is within the range [0..250,000];
  • string S is made only of the following characters: 'A', 'B', 'C', and/or 'D'.

1Example 1

Input
S = "CBACD"
Output
"C"
Explanation
Example 1 illustration
One of the possible sequences of operations is as follows: CBACD -> CBA -> C

2Example 2

Input
S = "CABABD"
Output
""
Explanation
Example 2 illustration
One possible sequence of operations is: CABABD -> CABD -> CD -> (empty string)

3Example 3

Input
S = "ACBDACBD"
Output
"ACBDACBD"
Explanation
No operation can be applied to string S, so the function should return "ACBDACBD".
public String solution(String S) {
  // write your code here
}
Input

S

"CBACD"

Output

"C"

Sign in to submit your solution.