Java: replacement in a string according to multiple rules

Question

I have the following task. There is a string. I must do replacement in it according to 6 rules till it is possible to make a replacement in a string.

The solution I found is below. It works right. The problem is that its performance is low. How else can I make replacement according to multiple rules? Is there any algorithm?

P.S. This task is from codility site. I got 100% correctness and 25% performance for my solution.

class Test {

    private Map<String,String> rules;

    private void initRules(){
        rules=new HashMap<>();
        rules.put("AB", "AA");
        rules.put("BA", "AA");
        rules.put("CB", "CC");
        rules.put("BC", "CC");
        rules.put("AA", "A");
        rules.put("CC", "C");
    }

    public String test(String S) {
        initRules();
        loop:while(true){
            String oldString=S;
            for (Map.Entry<String, String> rule : rules.entrySet())
            {
                S=S.replace(rule.getKey(), rule.getValue());
            }
            if (oldString==S){
                break loop;
            };
        }
        return S;
    }
}

 public class NewMain {

    public static void main(String[] args) {
        Test test=new Test();
        System.out.println("Result:"+test.test("ABBCC"));;
    }

}

Answer 1

Here is an algorithm you can use:

Assumption: String consists of only (A,B,C)

If string is composed of B's only (no A/C), output = input string.

Otherwise:

Divide the string in the following way. If a substring consists of (B,A) or (B,C), divide them. Replace with A and C respectively. That will be the answer.

eg. Let the string be: "BBBAABABBBCCBCBBCACB". This will be divided as:

"BBBAABABBB" "CCBCBBC" "A" "CB"

And this will result in output string as: ACAC

Basically, just ignore all B's and replace clusters of A's with A and clusters of C's with C.

Answer 2

You can impliment a recursive algorythm for this. Then you can reduce the rules and apply. For instance AB -> AA, AA -> A then AB->A Then the answer would be

public static String stringReduce(String s){
  String transformed = s.replace("AA", "A").replace("CC", "C")
   .replace("BC", "C").replace("CB", "C").replace("BA", "A")
   .replace("AB", "A");

  if(transformed.equals(s)){
    return transformed;
  }
  else{
    return stringReduce(transformed);
  }
}

Answer 3

I prefer do while loop instead of recursion :

Here is the answer :

public String stringReduce(String input) {
    String previous;
    do {
        previous = input;
        input = input.replace("AA", "A").replace("CC", "C").replace("BC", "C").replace("CB", "C")
                .replace("BA", "A").replace("AB", "A");
    } while (!previous.equals(input));
    return input;
}