B - String Shifting Editorial by en_translator


Let \(N\) be the length of \(S\). Also, denote by \(S_i\) the \(i\)-th \((1 \leq i \leq N)\) character of \(S\).

Performing right shift once is equivalent to performing left shift \((N-1)\) times. Thus, we can assume that we only perform left shifts. Moreover, performing right shift \(N\) times results in the original string, so we can assume that we perform left shift between \(0\) and \(N-1\) times, inclusive.

IF we perform left shift \(k \, (1 \leq k \leq N - 1)\) times, we obtain a string expressed as \(S_{k+1} \ldots S_{N} S_1 \ldots S_{k}\). It is sufficient to enumerate (at most \(N\)) possible strings and find the lexicographically smallest / largest string.

Sample code (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';
}

Sample code (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))

posted:
last update: