STRINGSHIFT - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given a string. You can choose a substring of it and replace each character by the next Latin one cyclically (i.e. a\to b\to c\to\ldots\to y\to z\to a).
Find the lexicographically minimal final string after doing this at most once.

EXPLANATION:

Cyclically shifting a character upward by 1 will always make it lexicographically larger, unless it’s z \to a.

So,

  • If the string doesn’t contain any occurrence of z, it’s optimal to not do anything.
    The answer is the original string itself.
  • Otherwise, let L be the leftmost index containing a z.
  • Let R \gt L be the leftmost index after L that doesn’t contain a z.
  • Then, it’s optimal to choose the subarray [L, R-1] to operate on.

Essentially, we choose the leftmost block of z’s and convert them all to a, without incrementing any other element.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = list(input())
    
    for i in range(n):
        if s[i] != 'z': continue
        for j in range(i, n):
            if s[j] == 'z':
                s[j] = 'a'
            else:
                break
        break
    print(''.join(s))