Scale Engineer

Lexicographically Smallest String After Substring Operation

Med
#2460Time: 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: O(n). We need to store the character array and the resulting strings, each of which requires O(n) space.2 companies
Patterns
Greedy
Data structures
String
Companies
AgodaIBM

Prompt

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 * 105
  • s consists of lowercase English letters

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(n). We need to store the character array and the resulting strings, each of which requires O(n) space.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem