solution

$O({|S|}^2)$回BAをABに置換すればよい。$O({|S|}^3)$。

implementation

#!/bin/sed -f
:
s/BA\(.*\)/AB\1-/
t
s/\w*/0/
:1
s/-/<<123456789-01>/
s/\s*\(.\)<.*\1\(-*.\).*>/\2/
t1