Contest Duration: - (local time) (100 minutes) Back to Home

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: