\(S\) の長さを \(N\) とします。また、\(S\) の \(i \, (1 \leq i \leq N)\) 番目の文字を \(S_i\) で表します。

右シフトを \(1\) 回行うことは、左シフト を \(N-1\) 回行うことと同じです。そのため、左シフトのみを行うとしてよいです。さらに、左シフトを \(N\) 回行うと元の文字列に戻るため、左シフトを行う回数は \(0\) 回以上 \(N-1\) 回以下であるとしてよいです。

左シフトを \(k \, (1 \leq k \leq N - 1)\) 回行って得られる文字列は \(S_{k+1} \ldots S_{N} S_1 \ldots S_{k}\) と表せます。得られる文字列（高々 \(N\) 通り）を列挙し、その中で辞書順最小 / 最大のものを求めればよいです。

実装例 (C++) :

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = size(s);
    vector<string> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = s.substr(i, n - i) + s.substr(0, i);
    }
    cout << *min_element(begin(v), end(v)) << '\n';
    cout << *max_element(begin(v), end(v)) << '\n';
}

実装例 (Python) :

s = input()
n = len(s)
v = []
for k in range(0, n):
  v.append(s[k:n] + s[0:k])
print(min(v))
print(max(v))