We can rotate a string any number of times

We need to find the minimum possible string lexicographically.

E.g. inp — BCABDADAB op — ABBCABDAD

This is doable by Booth's algorithm in O(n).

I couldnt quite understand the way it is being done...can someone please help?

Link to algorithm

Link to complete question