Lexicographically Smallest String After Substring Operation solution and explanation
IBM
7 more videos on this problem
Lexicographically Smallest String After Substring Operation | Leetcode 2734 | Weekly 349Tech Courses · 6:29 · 1K views
Leetcode Weekly contest 349 - Medium - Lexicographically Smallest String After Substring OperationPrakhar Agrawal · 9:33 · 1K views
2734. Lexicographically Smallest String After Substring Operation (Leetcode Medium)Programming Live with Larry · 7:25 · 939 views
6465. Lexicographically Smallest String After Substring Operation | Leetcode | Weekly Contest 349.Optimization · 0:26 · 767 views
Leetcode 6465. Lexicographically Smallest String After Substring Operation Solution || Java CodeJatin Yadav · 0:59 · 484 views
LEXICOGRAPHICALLY SMALLEST STRING AFTER SUBSTRING OPERATIION | WEEKLY CONTEST | LEETCODE | 2734 |TechRats official · 10:40 · 314 views
Lexicographically Smallest String After Substring Operation 2734 LeetcodeAnubhav Ghosh · 5:45 · 228 views
leetcode 2734.Lexicographically Smallest StrAfter Substring Operation - leftmost sub str without aCode-Yao · 15:54 · 33 views
The problem
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 * 105sconsists of lowercase English letters
Approach overview
Problem Overview: You are given a lowercase string and can choose exactly one non-empty substring. For every character in that substring, decrease it by one in the alphabet ('b' → 'a', 'a' → 'z'). The goal is to produce the lexicographically smallest possible string after the operation.
Approach 1: Single Scan with Immediate Replacement (O(n) time, O(1) space)
This greedy strategy scans the string from left to right and looks for the first character that is not 'a'. Once found, you start a substring and keep decrementing characters until you hit another 'a'. Decreasing earlier characters has the strongest effect on lexicographic order, so starting at the first non-'a' position guarantees the smallest possible prefix. Each character in the selected segment is reduced by one using a simple character shift. If the string consists entirely of 'a', the optimal move is to change the last character to 'z'. This approach performs a single pass and uses constant extra memory.
This technique relies on a greedy observation: modifying the earliest possible position produces the biggest lexicographic improvement. The logic mainly involves iterating over characters and performing in-place updates, making it a clean example of greedy reasoning applied to a string manipulation problem.
Approach 2: Reverse String and Apply (O(n) time, O(n) space)
Another way to reason about the operation is by reversing the string and processing the transformation from the end. After reversing, you locate the first character that can be decremented without breaking the greedy condition and apply the same decrement logic over the contiguous segment. Once the transformation is complete, reverse the string again to restore the original order. This approach simplifies certain implementations where processing from the tail is more intuitive.
Although it introduces an extra reverse step and temporary storage, the overall time complexity remains linear. The algorithm still performs constant work per character and maintains predictable behavior for edge cases such as strings composed entirely of 'a'.
Recommended for interviews: The single-scan greedy solution is what most interviewers expect. It demonstrates that you understand how lexicographic order works and why modifying the earliest non-'a' character minimizes the result. Mentioning the reverse-processing idea can show deeper reasoning, but implementing the linear greedy scan clearly signals strong problem-solving skills.
Approach 1: Single Scan with Immediate Replacement
This approach involves scanning through the string once and beginning the replacement operation the moment we encounter the first character that is greater than 'a'. We continue replacing characters until either a 'a' is encountered again or we reach the end of the string. This single-pass approach ensures the transformation is performed instantaneously when the optimal condition is detected.
def smallest_string_after_operation(s):
chars = list(s)
has_changed = False
for i in range(len(chars)):
if chars[i] > 'a':
chars[i] = chr(ord(chars[i]) - 1)
has_changed = True
elif has_changed:
break
return ''.join(chars)
print(smallest_string_after_operation("cbabc"))
public class LexicographicallySmallestString {
public static String smallestStringAfterOperation(String s) {
char[] chars = s.toCharArray();
boolean hasChanged = false;
for (int i = 0; i < chars.length; i++) {
if (chars[i] > 'a') {
chars[i]--;
hasChanged = true;
} else if (hasChanged) {
break;
}
}
return new String(chars);
}
public static void main(String[] args) {
System.out.println(smallestStringAfterOperation("cbabc"));
}
}
#include <iostream>
#include <string>
void smallestStringAfterOperation(std::string &s) {
bool hasChanged = false;
for (char &c : s) {
if (c > 'a') {
c -= 1;
hasChanged = true;
} else if (hasChanged) {
break;
}
}
}
int main() {
std::string s = "cbabc";
smallestStringAfterOperation(s);
std::cout << s << std::endl;
return 0;
}
function smallestStringAfterOperation(s) {
let chars = s.split('');
let hasChanged = false;
for (let i = 0; i < chars.length; i++) {
if (chars[i] > 'a') {
chars[i] = String.fromCharCode(chars[i].charCodeAt(0) - 1);
hasChanged = true;
} else if (hasChanged) {
break;
}
}
return chars.join('');
}
console.log(smallestStringAfterOperation("cbabc"));
#include <stdio.h>
#include <string.h>
void smallest_string_after_operation(char *s) {
int has_changed = 0; // Flag to indicate if a change has been made
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] > 'a') {
s[i]--;
has_changed = 1;
} else if (has_changed == 1) { // If change has started, stop at 'a'
break;
}
}
}
int main() {
char s[] = "cbabc";
smallest_string_after_operation(s);
printf("%s\n", s);
return 0;
}
using System;
public class Solution {
public static string SmallestStringAfterOperation(string s) {
char[] chars = s.ToCharArray();
bool hasChanged = false;
for (int i = 0; i < chars.Length; i++) {
if (chars[i] > 'a') {
chars[i]--;
hasChanged = true;
} else if (hasChanged) {
break;
}
}
return new string(chars);
}
public static void Main() {
Console.WriteLine(SmallestStringAfterOperation("cbabc"));
}
}In this Python solution, the string is first converted to a list of characters. The iteration then decrements the character if it’s greater than 'a' and sets a flag. If an 'a' is encountered after changes, the operation stops. Finally, a string is constructed back from the list.
Time Complexity: O(n), owing to the single loop traversal.
Space Complexity: O(n), for the list of characters.
Approach 2: Reverse String and Apply
This method involves reversing the string and applying the replacement operation in reverse order. It ensures that any leading 'a' characters in the reversed string don't interfere with the operation, potentially providing an alternative path to reach the solution efficiently.
def reverse(s):
return s[::-1]
def smallest_string_after_operation(s):
s = reverse(s)
chars = list(s)
has_changed = False
for i in range(len(chars)):
if chars[i] > 'a':
chars[i] = chr(ord(chars[i]) - 1)
has_changed = True
elif has_changed:
break
return reverse(''.join(chars))
print(smallest_string_after_operation("cbabc"))
public class ReverseOperation {
public static String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}
public static String smallestStringAfterOperation(String s) {
s = reverse(s);
char[] chars = s.toCharArray();
boolean hasChanged = false;
for (int i = 0; i < chars.length; i++) {
if (chars[i] > 'a') {
chars[i]--;
hasChanged = true;
} else if (hasChanged) {
break;
}
}
return reverse(new String(chars));
}
public static void main(String[] args) {
System.out.println(smallestStringAfterOperation("cbabc"));
}
}
#include <iostream>
#include <string>
std::string reverse(const std::string &s) {
return std::string(s.rbegin(), s.rend());
}
void smallestStringAfterOperation(std::string &s) {
s = reverse(s);
bool hasChanged = false;
for (char &c : s) {
if (c > 'a') {
c -= 1;
hasChanged = true;
} else if (hasChanged) {
break;
}
}
s = reverse(s);
}
int main() {
std::string s = "cbabc";
smallestStringAfterOperation(s);
std::cout << s << std::endl;
return 0;
}
function reverse(s) {
return s.split('').reverse().join('');
}
function smallestStringAfterOperation(s) {
s = reverse(s);
let chars = s.split('');
let hasChanged = false;
for (let i = 0; i < chars.length; i++) {
if (chars[i] > 'a') {
chars[i] = String.fromCharCode(chars[i].charCodeAt(0) - 1);
hasChanged = true;
} else if (hasChanged) {
break;
}
}
return reverse(chars.join(''));
}
console.log(smallestStringAfterOperation("cbabc"));
#include <stdio.h>
#include <string.h>
void reverse_string(char *s) {
int n = strlen(s);
for (int i = 0; i < n / 2; i++) {
char temp = s[i];
s[i] = s[n - i - 1];
s[n - i - 1] = temp;
}
}
void smallest_string_after_operation(char *s) {
reverse_string(s); // Reverse the initial string
int has_changed = 0;
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] > 'a') {
s[i]--;
has_changed = 1;
} else if (has_changed == 1) {
break;
}
}
reverse_string(s); // Reverse back the string
}
int main() {
char s[] = "cbabc";
smallest_string_after_operation(s);
printf("%s\n", s);
return 0;
}
using System;
public class ReverseOperation
{
public static string Reverse(string s)
{
char[] arr = s.ToCharArray();
Array.Reverse(arr);
return new string(arr);
}
public static string SmallestStringAfterOperation(string s)
{
s = Reverse(s);
char[] chars = s.ToCharArray();
bool hasChanged = false;
for (int i = 0; i < chars.Length; i++)
{
if (chars[i] > 'a')
{
chars[i]--;
hasChanged = true;
}
else if (hasChanged)
{
break;
}
}
return Reverse(new string(chars));
}
public static void Main()
{
Console.WriteLine(SmallestStringAfterOperation("cbabc"));
}
}This Python implementation reverses and processes in sequence, respecting the switched frame. Crucially, the string continues being modified post reversal restores a regular view.
Time Complexity: O(n), when considering each reverse phase and goes from end to end.
Space Complexity: O(n), for character manipulation.
Approach 3: Greedy Algorithm
We can traverse the string s from left to right, find the position i of the first character that is not 'a', and then find the position j of the first 'a' character starting from i. We decrement each character in s[i:j], and finally return the processed string.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
function smallestString(s: string): string {
const cs: string[] = s.split('');
const n: number = cs.length;
let i: number = 0;
while (i < n && cs[i] === 'a') {
i++;
}
if (i === n) {
cs[n - 1] = 'z';
return cs.join('');
}
let j: number = i;
while (j < n && cs[j] !== 'a') {
const c: number = cs[j].charCodeAt(0);
cs[j] = String.fromCharCode(c - 1);
j++;
}
return cs.join('');
}func smallestString(s string) string {
n := len(s)
i := 0
for i < n && s[i] == 'a' {
i++
}
cs := []byte(s)
if i == n {
cs[n-1] = 'z'
return string(cs)
}
j := i
for j < n && cs[j] != 'a' {
cs[j] = cs[j] - 1
j++
}
return string(cs)
}impl Solution {
pub fn smallest_string(s: String) -> String {
let mut cs: Vec<char> = s.chars().collect();
let n = cs.len();
let mut i = 0;
while i < n && cs[i] == 'a' {
i += 1;
}
if i == n {
cs[n - 1] = 'z';
return cs.into_iter().collect();
}
let mut j = i;
while j < n && cs[j] != 'a' {
cs[j] = ((cs[j] as u8) - 1) as char;
j += 1;
}
cs.into_iter().collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Single Scan with Immediate Replacement | Time Complexity: O(n), owing to the single loop traversal. |
| Reverse String and Apply | Time Complexity: O(n), when considering each reverse phase and goes from end to end. |
| Greedy Algorithm | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Scan with Immediate Replacement | O(n) | O(1) | Best general solution. Minimal memory and optimal greedy logic. |
| Reverse String and Apply | O(n) | O(n) | Useful when implementing transformations from the end or when reverse traversal simplifies reasoning. |
Frequently asked questions
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.
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.
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.
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.