Lexicographically Smallest String After Substring Operation

Medium
1248.

Lexicographically Smallest String After Substring Operation

Lexicographically Smallest String After Substring Operation is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.

You are given a lowercase string s. Perform the following operation exactly once: choose a non-empty substring of s and replace every letter in it by the previous letter of the alphabet, where 'a' becomes 'z'.

Return the lexicographically smallest string you can obtain.

Example 1

Input
s = "kairo"
Output
jairo
Explanation
Shift just the `k`; extending the substring onto the `a` would turn it into `z`.

Example 2

Input
s = "abba"
Output
aaaa
Explanation
Shift the substring `"bb"`.

Example 3

Input
s = "aaa"
Output
aaz
Explanation
Some letter must change, and an `a` can only become `z`; changing the last one costs the least.

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var smallestString = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Lexicographically Smallest String After Substring Operation Solution

Lexicographically Smallest String After Substring Operation solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Lexicographically Smallest String After Substring Operation is a medium coding problem on strings and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a lowercase string s. Perform the following operation exactly once: choose a non-empty substring of s and replace every letter in it by the previous letter of the alphabet, where 'a' becomes 'z'.

Return the lexicographically smallest string you can obtain.

Example 1

Input: s = "kairo"
Output: jairo
Explanation: Shift just the `k`; extending the substring onto the `a` would turn it into `z`.

Example 2

Input: s = "abba"
Output: aaaa
Explanation: Shift the substring `"bb"`.

Example 3

Input: s = "aaa"
Output: aaz
Explanation: Some letter must change, and an `a` can only become `z`; changing the last one costs the least.

Constraints

  • 1 <= s.length <= 3 * 10^5
  • s consists of lowercase English letters

Hints for Lexicographically Smallest String After Substring Operation

  1. Hint 1

    Shifting any letter other than a makes it smaller; shifting an a makes it much larger.

  2. Hint 2

    Leading as are already as small as possible — leave them. Start at the first letter that is not a.

  3. Hint 3

    From there, shift every letter up to (not including) the next a. If the string is all as, you are forced to turn the last one into z.

How to solve Lexicographically Smallest String After Substring Operation

Decrease the first maximal block of non-a letters. Everything before it is already optimal, and stopping before the next a avoids turning it into z.

Approach

  1. Find the first index i with s[i] != 'a'.
  2. If there is none, change the last character to 'z' and return.
  3. Otherwise, starting at i, replace each letter with its predecessor while the letter is not 'a'; stop at the first 'a' or at the end.

Why it works

The leading as cannot get smaller, and touching any of them makes that position a z, so the earliest position we can improve is the first non-a; improving it beats every string that leaves it alone. Continuing over further non-a letters only makes more positions smaller, while including an a would make that position larger, so the block stops right before the next a. When the string is all as some letter must become z, and putting it at the last position keeps the longest possible prefix of as.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • The operation is mandatory — an all-a string cannot stay unchanged.
  • Do not continue past an a: it would wrap around to z.
  • Only one substring may be chosen, so only the first non-a block changes.

Reference solution

Python

def smallestString(s: str) -> str:
    a = list(s)
    n = len(a)
    i = 0
    while i < n and a[i] == "a":
        i += 1
    if i == n:
        a[-1] = "z"
        return "".join(a)
    while i < n and a[i] != "a":
        a[i] = chr(ord(a[i]) - 1)
        i += 1
    return "".join(a)

Java

public static String smallestString(String s) {
    char[] a = s.toCharArray();
    int n = a.length, i = 0;
    while (i < n && a[i] == 'a') i++;
    if (i == n) {
        a[n - 1] = 'z';
        return new String(a);
    }
    while (i < n && a[i] != 'a') {
        a[i]--;
        i++;
    }
    return new String(a);
}

C++

string smallestString(string s) {
    int n = s.size(), i = 0;
    while (i < n && s[i] == 'a') i++;
    if (i == n) {
        s[n - 1] = 'z';
        return s;
    }
    while (i < n && s[i] != 'a') {
        s[i]--;
        i++;
    }
    return s;
}

JavaScript

var smallestString = function(s) {
    var a = s.split(""), n = a.length, i = 0;
    while (i < n && a[i] === "a") i++;
    if (i === n) {
        a[n - 1] = "z";
        return a.join("");
    }
    while (i < n && a[i] !== "a") {
        a[i] = String.fromCharCode(a[i].charCodeAt(0) - 1);
        i++;
    }
    return a.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms