Smallest Rotation
Programming Interview
Hard
9 views
Problem Description
A string s is provided. Consider all rotations of s. Output the lexicographically smallest rotation.
Output Format
One line smallest rotation.
Official Solution
import sys
s=sys.stdin.read().strip()
if not s: sys.exit(0)
ss=s+s
n=len(s)
i=0
j=1
k=0
while i<n and j<n and k<n:
a=ss[i+k]
b=ss[j+k]
if a==b:
k+=1
continue
if a>b:
i=i+k+1
if i<=j:
i=j+1
else:
j=j+k+1
if j<=i:
j=i+1
k=0
start=min(i,j)
sys.stdout.write(ss[start:start+n])
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!