Efficient algorithm perl or python

Question

Interviewer asked a question in an interview to write fast & efficient algorithm for below function,

Problem: Write a function to parse a given string for below given rules & produce final parsed string as output

write a function which will accepts string as input, string length will be in between [0..2000000000]

string should be made from only 'A','B' & 'C' characters like 'AAA' ,'ABCABC','AAAABBBBABAAACCCA'

Transformation Rules:

1) 'AB' -> 'AA'
2) 'AC' -> 'AA'
3) 'AA' -> 'A'
4) 'CC' -> 'C'
5) 'BC' -> 'BB'
6) 'BB' -> 'B'

Apply all above 6 rules randomly on given string each at a time and make final transformed string as output

For example input to Function is: 'ABCAAB' string

ABCAAB -> AACAAB [AB = AA]
AACAAB -> ACAAB [AA = A]
ACAAB -> AAAAB [AC = AA]
AAAAB -> AAAB [AA = A]
AAAB -> AAB [AA = A]
AAB -> AB [AA = A]
AB -> AA [AB = AA]
AA -> A [AA = A]

Final result: 'A'
Because we can not apply any more rules to the string now.

My Answer was like (pseudocode):

sub myFunc {
my $str = @_;
flag = 1
while(flag ==1) {
    if ($str =~ /AB/){
    $str =~ s/AB/AA/;
    next;
    }
    elsif($str =~ /AC/){
    $str =~ s/AC/AA/;
    next;
    }
    elsif($str =~ /AA/){
    $str =~ s/AA/A/;
    next;
    }
    elsif($str =~ /CC/){ 
    $str =~ s/CC/C/;
    next;
    }
    elsif($str =~ /BC/){ 
    $str =~ s/BC/BB/;
    next;
    }
    elsif($str =~ /BB/){ 
    $str =~ s/BB/B/;
    next;
    }
    else
    {
        flag = 0
    }
} //while
 return $str;
} //func

Can someone suggest better algorithm & approach for above problem ?

Answer 1

Rules 1 to 3 will discard any character following an A.
Rules 5 and 6 will discard any B and C following a B.
Rule 4 will discard any C following a C. The order of the substitutions does not matter.

So after processing the string will be one of C, CB, CA, CBA, B, BA, A.

A single scan of the string will suffice. If you see a C, keep it and skip the next C's; then if you see a B, keep it and skip the next B's; then if you see an A keep it and stop.

The given example ABCAAB immediately yields A.

Solutions with explicit application of the rules and multiple passes are unacceptable as their behavior can be O(N²) or even O(N³), while N=2000000000.