The problem asks to find the lexicographically (Dictionary Order) smallest sequence from a given circular sequence. What does it mean?

Take the string $s = CGAGTCAGCT$. As it is a circular string, it has no fixed starting point. We can start at any index and then continue iterating to next character until we have a string $s^\prime$ which has a length equal to $s$.

For example, we can start at index $3$ of $s$ and construct the string $s^\prime = GTCAGCTCGA$. Notice how $s^\prime$ wraps around when it has reached the end of $s$. But is this the lexicographically smallest string that we can construct from $s$? Actually, no. If we start from index $6$, we get $s^\prime = AGCTCGAGTC$ which is the lexicographically smallest string. Starting from index $2$ gives $s^{\prime\prime} = AGTCAGCTCG$, but $s^{\prime} < s^{\prime\prime}$, i.e. $s^\prime$ is lexicographically smaller than $s^{\prime\prime}$. Or in other words, $s^\prime$ comes before $s^{\prime\prime}$ in dictionary order.

We denote the lexicographically smallest string as $s^\prime$. So how can we find $s^\prime$? One naive strategy is to start from all index $i$ of $s$ such that $0 \leq i < s.\textrm{length}$ and construct a circular string of length $s.\textrm{length}$ starting at $i$. We denote the circular string constructed in each iteration as $s^{\prime\prime}$. If $s^{\prime\prime} < s^\prime$, then we assign $s^\prime = s^{\prime\prime}$.

This is actually a viable approach. As $s.\textrm{length}$ can be at most $100$, the above approach requires $100 * 100 = 10^4$ iterations per test case, which will pass the time limit. But can we do better?

Yes, we actually can! Notice that not all of the starting index of $s$ will yield a valid result. For example, if $s = CGAGTCAGCT$, then we know starting from index $0$ (containing letter $C$) or index $1$ (containing letter $G$) will not result in lexicographically smallest string. We actually have to start from the index that contains lexicographically smallest character. In this example, it’s index $2$ and index $6$. This will give us two circular strings, but the one starting from index $6$ is the answer. This approach saves us from constructing circular strings that are of no interest.

So, first we have to find the indices of the lexicographically smallest character. Then from those indices, we’ll construct the circular strings. The rest of this approach is similar to the one above. This approach actually has the same worst case time complexity as the former and it occurs when all of the characters in $s$ are lexicographically smallest (e.g. $s = AAA$). But if the characters occur with a uniform distribution, then in general this approach will be faster than the former.

Here’s the implementation in C++: