SHORTSPELL - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given a string S, find the lexicographically smallest string that can be obtained by deleting exactly one character from S.

EXPLANATION:

Deleting S_i can be thought of as essentially moving the character S_{i+1} one step to the left (for the sake of comparison).
You can thus see that:

  • If S_i \leq S_{i+1}, it’s never optimal to delete S_i (you’re replacing S_i with something larger than it, might as well delete S_{i+1} instead.
  • If S_i \gt S_{i+1}, it’s good to delete S_i since we put a smaller value at index i.

So, let i be the smallest index such that S_i \gt S_{i+1}.

  • If i exists, delete S_i and print the remaining string.
  • Otherwise, S is sorted - in which case it’s best to delete the last character.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    ch = -1
    for i in range(n-1):
        if s[i] > s[i+1]:
            ch = i
            break
    if ch == -1: print(s[:n-1])
    else: print(s[:ch] + s[ch+1:])