Efficient algorithm perl or python

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.

You can repeat substitution while it matches transformation rules,

my %h = (
  'AB' => 'AA',
  'AC' => 'AA', 
  'AA' => 'A', 
  'CC' => 'C', 
  'BC' => 'BB', 
  'BB' => 'B', 
);
my $s = 'ABCAAB';

1 while $s =~ s/(AB|AC|AA|CC|BC|BB)/$h{$1}/; # also without /g switch
print $s;

output

A

here is a python solution:

In [34]: import ranodm
In [35]: rules = {"AB":"AA",'AC':'AA','AA':'A','CC':'C','BC':'BB','BB':'B'}

In [36]: keys = rules.keys()

In [37]: keys
Out[37]: ['AA', 'AC', 'AB', 'BB', 'BC', 'CC']

In [38]: mystr = 'ABCAAB' 

In [42]: while len(mystr)>=2:
    r = random.choice(keys) #choose one rule randomly 
    mystr = mystr.replace(r,rules[r])
   ....:   

In [43]: mystr
Out[43]: 'A'

Yves Daoust's answer is right, makes no sense to simulate it. Seems like a trick question and that you were supposed to realize that and understand the behavior and implement it directly.

Yves' method works, but here's an actual implementation of a similar one:

def transform(string):
    a = string.find('A') + 1
    b = string.find('B', 0, a or len(string)) + 1
    return 'C' * string.startswith('C') + 'B' * (b>0) + 'A' * (a>0)

I search for the first 'A', then search for a 'B' left of it (or in the whole string, if there was no 'A'). That tells me whether 'B' and 'A' belong into the output. For 'C' I just need to check the start of the string. While I potentially scan the whole string twice rather than just once like Yves suggests, using the find function makes pretty it fast, about a 100 times faster than just looping over the string "by hand" and just looking for an 'A' (which is only at the end of my teststring):

>>> from timeit import timeit
>>> s = 'C' * 100000000 + 'BA'

>>> timeit(lambda: transform(s), number=1)
0.10583857561359977

>>> timeit(lambda: next(x for x in s if x == 'A'), number=1)
10.957446603791382

You could do it with just one scan by using lstrip('C') to find the first non-'C' character, and that's faster than doing it by hand, but that uses extra memory and is still much slower than find:

>>> timeit(lambda: s.lstrip('C'), number=1)
2.411250071361735

Regular expressions could probably also do it, but even just scanning my teststring once just looking for 'A' takes longer than my whole transform:

>>> timeit(lambda: re.search('A', s), number=1)
0.13403880409939006