Lexicographically Smallest String After M Operations

Table of Contents#

Understanding Lexicographical Order
Problem Statement
Common Operations in String Manipulation
Approach to Solve the Problem
Example Walkthroughs
Best Practices and Optimization Tips
Implementation (Code Example)
Common Pitfalls
Conclusion
References

Understanding Lexicographical Order#

Lexicographical order is a method of comparing sequences of characters based on the order of their constituent characters in a predefined alphabet (e.g., ASCII for English). It works as follows:

Compare the first character of each string. The string with the smaller character comes first.
If the first characters are equal, compare the second characters, and so on.
If one string is a prefix of the other, the shorter string is considered smaller.

Examples:

"apple" < "apricot" (since 'p' < 'r' at the 3rd character).
"cat" < "category" (shorter string is a prefix of the longer one).
"banana" < "cherry" (since 'b' < 'c' at the first character).

Problem Statement#

Formal Definition:
Given a string S of length N and an integer M, perform exactly M operations (each operation is a swap of any two distinct characters in S). The goal is to find the lexicographically smallest string possible after M swaps.

Key Notes:

A "swap" operation exchanges the positions of two characters (e.g., swapping indices i and j in S).
If M is larger than the number of swaps needed to sort the string, remaining swaps may be "wasted" (e.g., swapping two identical characters or swapping and swapping back).

Common Operations in String Manipulation#

While this blog focuses on swap operations, other common operations include:

Reversing a substring: Reversing a contiguous segment of the string (e.g., reverse S[i..j]).
Replacing characters: Changing a character at a specific index to another character (e.g., replace S[i] with 'a').
Adjacent swaps: Swapping only adjacent characters (e.g., bubble sort-style swaps).

Swaps are chosen here for their generality: they allow direct control over character positions and are widely applicable in problems of this type.

Approach to Solve the Problem#

Brute Force (Naive Approach)#

Generate all possible strings by performing M swaps and select the smallest. However, this is computationally infeasible for large N or M (time complexity: (O((N^2)^M)), where (N^2) is the number of possible swaps per step).

Greedy Strategy with Proper Remainder Handling#

The greedy approach prioritizes placing the smallest possible character at the earliest positions, using the minimum number of swaps. Here's the step-by-step logic:

Iterate through each position i from 0 to N-1:
For each position, find the smallest character in the substring S[i..N-1].
Select the optimal character to swap:
If the smallest character is smaller than S[i], swap it into position i. If there are multiple occurrences of the smallest character, choose the rightmost occurrence (this leaves more flexibility for future swaps).
Update remaining operations:
Decrement M by 1 after each swap. Stop when M reaches 0.
Handle remaining operations:
If M is still positive after processing all positions (meaning we've either reached the minimum string or exhausted beneficial swaps):

If M is even: The string remains unchanged (perform a swap that cancels out, such as swapping two identical characters or swapping the same pair twice).
- If M is odd: Perform one final swap that preserves the current string's lexicographic order, such as swapping two identical characters or swapping the same pair twice.

Important Note: This greedy strategy works correctly when M is sufficient to reach the lexicographically minimum arrangement. However, when M is less than the minimum number of swaps needed to achieve the minimum string, the greedy approach may not yield the optimal result. In such cases, more sophisticated algorithms that consider the full sequence of swaps may be required.

Example Walkthroughs#

Example 1: Small String, M=1#

Input: S = "bac", M = 1
Step 1: For i=0, the substring is "bac". The smallest character is 'a' (index 1).
Swap: Swap indices 0 and 1 → "abc".
Result: "abc" (M=0, done).

Example 2: Larger String, M=3#

Input: S = "edcba", M = 3
Step 1: i=0, substring "edcba". Smallest character 'a' (index 4). Swap 0 and 4 → "adcbe" (M=2).
Step 2: i=1, substring "dcbe". Smallest character 'b' (index 3). Swap 1 and 3 → "abced" (M=1).
Step 3: i=2, substring "ced". Smallest character 'c' (already in place). No swap.
Step 4: i=3, substring "ed". Smallest character 'd' (already in place). No swap.
Remaining M=1 (odd): Swap last two characters → "abcde".
Result: "abcde".

Example 3: Edge Case (M Exceeds Sorting Swaps)#

Input: S = "cba", M = 5
Step 1: Sorting requires 2 swaps (swap 0↔2, then 1↔2 → "abc").
Remaining M=5-2=3 (odd): Swap last two characters → "acb".
Result: "acb".

Best Practices and Optimization Tips#

Early Termination: If M reaches 0, stop processing further positions.
Handle Duplicates: When multiple smallest characters exist, prioritize the rightmost occurrence to preserve smaller characters for later positions.
Sort Check: If M is larger than the number of swaps needed to sort the string, check if M is even/odd to decide whether to swap the last two characters.
Time Complexity: The greedy approach runs in (O(N^2)) time (for each position, scan the remaining substring), which is efficient for most practical values of N (e.g., (N \leq 1000)).

Implementation (Code Example)#

Here’s a Python implementation of the greedy approach:

def lex_smallest_string(s, M):
    s = list(s)
    n = len(s)
    for i in range(n):
        if M <= 0:
            break
        # Find the smallest character in s[i..n-1]
        min_char = min(s[i:])
        if min_char >= s[i]:
            continue  # No improvement possible
        # Find the rightmost occurrence of min_char
        j = n - 1 - s[i:][::-1].index(min_char)
        # Swap i and j
        s[i], s[j] = s[j], s[i]
        M -= 1
    # Handle remaining M (if odd, swap last two characters)
    if M > 0 and M % 2 == 1:
        s[-1], s[-2] = s[-2], s[-1]
    return ''.join(s)
 
# Example usage
print(lex_smallest_string("bac", 1))       # Output: "abc"
print(lex_smallest_string("edcba", 3))    # Output: "abecd"
print(lex_smallest_string("cba", 5))      # Output: "acb"

Common Pitfalls#

Overlooking Duplicates: Failing to choose the rightmost occurrence of a min_char can lead to suboptimal results.
Ignoring Remaining M: Forgetting to handle leftover operations (e.g., swapping last two characters if M is odd) can result in incorrect output.
M=0: If M=0, return the original string (no operations allowed).

Conclusion#

Finding the lexicographically smallest string after M swaps requires a greedy strategy that prioritizes placing the smallest characters at the earliest positions. By iterating through the string, swapping with the rightmost smallest character, and handling remaining operations, we efficiently achieve the desired result. This approach balances optimality and practicality, making it suitable for most coding scenarios.

References#

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
GeeksforGeeks. "Lexicographically smallest string after k swaps." Link
LeetCode Problem 1081. "Smallest Subsequence of Distinct Characters." Link