Lexicographically Smallest String After Substring Operation

Lexicographically Smallest String After Substring Operation - Problem

String Greedy Medium

Given a string s consisting of lowercase English letters. You must perform exactly one operation:

Operation: Select any non-empty substring and 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.

Input & Output

Example 1 — Non-'a' Character

$ Input: s = "cba"

› Output: "bba"

💡 Note: We can select the substring "c" and change it to "b". The resulting string "bba" is lexicographically smallest possible.

Example 2 — All 'a' Characters

$ Input: s = "aaa"

› Output: "aaz"

💡 Note: Since all characters are 'a', we must change at least one. Changing the last 'a' to 'z' gives us "aaz", which is lexicographically smallest.

Example 3 — Mixed Characters

$ Input: s = "abcxyz"

› Output: "aacxyz"

💡 Note: The first non-'a' character is 'b' at position 1. Changing 'b' to 'a' gives "aacxyz".

Constraints

1 ≤ s.length ≤ 10⁵
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with lowercase letters

Find Optimal Position

Choose best substring to minimize result

Apply Operation

Decrement characters in chosen substring

Key Takeaway

🎯 Key Insight: To minimize lexicographically, change the leftmost character that can become smaller

Asked in

G Google 25 M Microsoft 18

The key insight is that to get the lexicographically smallest string, we should change the leftmost character that can be made smaller. The greedy approach finds the first non-'a' character and decrements it, or changes the last 'a' to 'z' if all characters are 'a'. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Substrings	O(n³)	O(n²)	Try every possible substring operation and find the lexicographically smallest result
Greedy - Optimal Single Pass	O(n)	O(n)	Find the leftmost non-'a' character and decrement it (or last 'a' if all are 'a')

Brute Force - Try All Substrings — Algorithm Steps

Step 1: Generate all possible non-empty substrings
Step 2: For each substring, create a new string with operation applied
Step 3: Compare all results and return the lexicographically smallest

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Try all O(n²) possible substrings

Apply Operation

Transform each character in substring

Compare Results

Find lexicographically smallest

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s) {
    int n = strlen(s);
    char* best = malloc((n + 1) * sizeof(char));
    int first = 1;
    
    // Try all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            // Create new string with operation on substring s[i:j]
            char* result = malloc((n + 1) * sizeof(char));
            strcpy(result, s);
            
            for (int k = i; k < j; k++) {
                if (result[k] == 'a') {
                    result[k] = 'z';
                } else {
                    result[k] = result[k] - 1;
                }
            }
            
            if (first || strcmp(result, best) < 0) {
                strcpy(best, result);
                first = 0;
            }
            
            free(result);
        }
    }
    
    return best;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings × O(n) string creation and comparison

⚠ Quadratic Growth

Space Complexity

O(n²)

Storing O(n²) different result strings for comparison

⚠ Quadratic Space

23.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Substrings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler