Lexicographically Smallest String After Substring Operation

MEDIUM

Description

Given a string s consisting of lowercase English letters. Perform the following operation:

Select any non-empty substring then replace every letter of the substring with the preceding letter of the English alphabet. For example, 'b' is converted to 'a', and 'a' is converted to 'z'.

Return the lexicographically smallest string after performing the operation.

Example 1:

Input: s = "cbabc"

Output: "baabc"

Explanation:

Perform the operation on the substring starting at index 0, and ending at index 1 inclusive.

Example 2:

Input: s = "aa"

Output: "az"

Explanation:

Perform the operation on the last letter.

Example 3:

Input: s = "acbbc"

Output: "abaab"

Explanation:

Perform the operation on the substring starting at index 1, and ending at index 4 inclusive.

Example 4:

Input: s = "leetcode"

Output: "kddsbncd"

Explanation:

Perform the operation on the entire string.

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of lowercase English letters

Approaches

Checkout 2 different approaches to solve Lexicographically Smallest String After Substring Operation. Click on different approaches to view the approach and algorithm in detail.

Brute-Force by Checking All Substrings

This approach considers every possible non-empty substring of the input string s. For each substring, it performs the specified operation to generate a new candidate string. It then compares all these candidate strings to find the lexicographically smallest one.

Algorithm

Initialize a variable smallestString to a value that is lexicographically larger than any possible result.
Use nested loops to iterate through all possible start indices i from 0 to n-1 and end indices j from i to n-1.
For each pair (i, j), construct a new string temp by applying the operation on the substring s[i...j].
To create temp:
- Take the prefix s.substring(0, i).
- Iterate k from i to j, transform s[k] to its predecessor (with 'a' wrapping around to 'z'), and append to a builder.
- Take the suffix s.substring(j + 1).
Compare temp with smallestString. If temp is lexicographically smaller, update smallestString = temp.
After checking all substrings, smallestString will hold the final answer.

The core idea is to exhaustively check all possibilities. There are O(n^2) possible non-empty substrings in a string of length n. We can define each substring by its start and end indices. The algorithm proceeds as follows:

public String smallestString(String s) {
    int n = s.length();
    String smallest = null;

    // Generate all possible non-empty substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // Substring is from i to j inclusive
            char[] chars = s.toCharArray();
            
            // Apply the operation on the substring
            for (int k = i; k <= j; k++) {
                if (chars[k] == 'a') {
                    chars[k] = 'z';
                } else {
                    chars[k]--;
                }
            }
            
            String current = new String(chars);
            
            // Keep track of the lexicographically smallest string found so far
            if (smallest == null || current.compareTo(smallest) < 0) {
                smallest = current;
            }
        }
    }
    return smallest;
}

This method is too slow for the given constraints because it checks every single one of the O(n^2) substrings and for each, it builds a new string which takes O(n) time.

Complexity Analysis

Time Complexity: O(n^3). There are O(n^2) substrings. For each substring, we create a new character array (O(n)) and then a new string (O(n)), leading to O(n) work per substring. The total time is O(n^2) * O(n) = O(n^3).Space Complexity: O(n). We need to store the character array and the resulting strings, each of which requires O(n) space.

Pros and Cons

Pros:

Conceptually simple and straightforward to implement.
Guaranteed to find the correct answer by checking all possibilities.

Cons:

Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints (n up to 3 * 10^5).

Code Solutions

Checking out 3 solutions in different languages for Lexicographically Smallest String After Substring Operation. Click on different languages to view the code.

class Solution {
public
  String smallestString(String s) {
    int n = s.length();
    int i = 0;
    while (i < n && s.charAt(i) == 'a') {
      ++i;
    }
    if (i == n) {
      return s.substring(0, n - 1) + "z";
    }
    int j = i;
    char[] cs = s.toCharArray();
    while (j < n && cs[j] != 'a') {
      cs[j] = (char)(cs[j] - 1);
      ++j;
    }
    return String.valueOf(cs);
  }
}

Video Solution

Watch the video walkthrough for Lexicographically Smallest String After Substring Operation

Patterns:

Greedy

Data Structures:

String

Companies:

Agoda |IBM |

Lexicographically Smallest String After Substring Operation

Description

Approaches

Brute-Force by Checking All Substrings

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Patterns:

Data Structures:

Companies:

On this page

Subscribe to Scale Engineer newsletter