Lexicographically Smallest String After Substring Operation Python/Java solution

In Python or Java, convert the string to a mutable structure (like a character array or list), scan for the first non-'a' character, and decrement characters until you hit an 'a'. The logic is identical across languages and runs in O(n) time.

What is the best approach for Lexicographically Smallest String After Substring Operation?

The optimal approach is a greedy single scan. Traverse the string from left to right and find the first character that is not 'a'. Start decrementing characters from that position until you encounter another 'a'. This produces the smallest lexicographic prefix possible and runs in O(n) time with O(1) extra space.

Is Lexicographically Smallest String After Substring Operation asked at Google/Amazon/Meta?

Problems based on greedy string transformations frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that require minimizing lexicographic order using a single operation are common because they test understanding of greedy reasoning and string manipulation.

What data structure is used in Lexicographically Smallest String After Substring Operation?

The problem mainly uses basic string or character array manipulation. No advanced data structures are required; the key idea is greedy scanning and in-place character updates while iterating through the string.

What is the time complexity of Lexicographically Smallest String After Substring Operation?

The optimal greedy solution runs in O(n) time because the algorithm scans the string once and performs constant work per character. Space complexity is O(1) since the transformation can be done in place without additional data structures.

Description Hints 2 Solution Video 6:29

2734. Lexicographically Smallest String After Substring Operation

Q: Is Lexicographically Smallest String After Substring Operation easy or hard?

The problem is rated Medium on LeetCode. The implementation is simple once the greedy insight is clear, but many candidates initially struggle to recognize that modifying the earliest non-'a' substring always leads to the smallest lexicographic result.

Q: How to solve Lexicographically Smallest String After Substring Operation in O(n)?

Perform a left-to-right scan and locate the first character that is not 'a'. Decrement each consecutive non-'a' character by one until an 'a' appears or the string ends. If the entire string is composed of 'a', modify the last character to 'z'. This guarantees the lexicographically smallest result in linear time.

Medium35.2% acceptance4 companies

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

Asked at 4 companies

IBM Agoda Goldman Sachs Amazon

Topics

Greedy String

Hints open one at a time

Hint 1

When a character is replaced by the one that comes before it on the alphabet, it makes the string lexicographically smaller, except for ‘a'.

Hint 2

Find the leftmost substring that doesn’t contain the character 'a' and change all characters in it.

6:29

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

2734. Lexicographically Smallest String After Substring Operation

Asked at 4 companies

Topics

Hints open one at a time

Similar problems