Description
Solutions
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'.

Example 1: 

Input:  S = "CBACD"
Output: "C" 
Explanation:

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

Example 2: 

Input:  S = "CABABD"
Output: "" 
Explanation:

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

Example 3: 

Input:  S = "ACBDACBD"
Output: "ACBDACBD" 
Explanation:

      No operation can be applied to string S, so the function should return "ACBDACBD".
Constraints:
    TO-DO
Thumbnail 0
Testcase
Result
Case 1

input:

output: