PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given a string A of length N.
Find any string of length N such that both the string and its reverse are lexicographically larger than A, or claim that none exist.
EXPLANATION:
For a string S to be larger than A, S should have a larger character than A at some index.
The largest possible character is 'z'. So, if every character of A equals 'z' it’s clearly impossible for any string to be strictly larger than it, and the answer is -1.
In every other case, a simple solution is to just print the string "zzz...zzz", i.e. 'z' repeated N times.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
if min(s) == 'z': print(-1)
else: print('z'*n)