Problem Brief

Zolando Manipulation

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:

class Solution { public 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

One of the possible sequences of operations is as follows: - CBACD → CCD → C

2Example 2

Input

S = "CABABD"

Output

Explanation

One possible sequence of operations is: - CABABD → CDD → ""

3Example 3

Input

S = "ACBDACBD"

Output

"ACBDACBD"

Explanation

No operation can be applied to string S, so the function should return "ACBDACBD".

Draft autosaves locally

public String solution(String S) {
  // write your code here 
    
}

Input

"CBACD"

Output

"C"