python - 高效的perl或python算法

面试官在面试中提问，为下面的函数编写快速高效的算法。
问题：编写一个函数来分析下面给定规则的给定字符串，并生成最终解析的字符串作为输出
编写一个接受字符串作为输入的函数，字符串长度将介于[0..2000000000]之间。
字符串只能由“a”、“b”和“c”等字符构成，如“aaa”、“abcabc”、“aaaaabaaccca”
转换规则：
1）‘AB’->‘AA’
2）‘AC’->‘AA’
3）‘a a’->‘a’
4）‘CC’->‘C’
5）‘BC’->‘BB’
6）‘b b’->‘b’
一次在给定的字符串上随机应用上述6个规则，并将最终转换的字符串作为输出
例如，函数的输入是：“abcaab”字符串
abcaab->aacaab[ab=aa]
a acaab->acaab[a a=a]
acaab->aaaab[ac=aa]
a aaab->aaab[a a=a]
a aab->aab[a a=a]
a ab->ab[a a=a]
AB->AA[AB=AA]
a a->a[aa=a]
最终结果：“A”
因为我们现在不能再对字符串应用任何规则了。
我的回答是（伪代码）：

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

有人能为上述问题提出更好的算法和方法吗？

最佳答案

规则1到3将丢弃a后面的任何字符。
第5条和第6条将放弃遵循A B的任何B和C。
规则4将丢弃C后面的任何C。替换顺序无关紧要。
所以在处理完之后，字符串将是C、CB、CA、CBA、B、BA、A中的一个。
对字符串进行一次扫描就足够了。如果你看到一个C，保持它并跳过下一个C；然后如果你看到一个B，保持它并跳过下一个B；然后如果你看到一个A，保持它并停止。
给出的示例abcaab立即生成a。
明确应用规则和多次传递的解决方案是不可接受的，因为它们的行为可以是O(N²)甚至O(N³)，而N=2000000000。