3216. Lexicographically Smallest String After a Swap

EasyGreedyString

Problem Description

Given a string s containing only digits, the task is to return the lexicographically smallest string that can be obtained after swapping adjacent digits in s with the same parity at most once. Digits have the same parity if both are odd or both are even. For example, both 5 and 9 are odd, and 2 and 4 are even, thus having the same parity. However, 6 and 9 have different parities.

Intuition

To solve this problem, a greedy strategy is employed where we traverse the string s from left to right. For each pair of adjacent digits, we check if they have the same parity. If they do, we evaluate whether swapping them results in a lexicographically smaller string, specifically checking if the left digit is larger than the right one. If so, we swap these digits since this will yield a smaller string. This step should be executed at most once, after which we return the newly formed string. If no such pair exists after the traversal, the original string is already in its smallest possible order, and we return it as is.

Learn more about Greedy patterns.

Solution Approach

The solution employs a simple greedy algorithm combined with a simulation of swaps. Here's how it is implemented:

Traversal and Comparison: Iterate over the string s from left to right, considering pairs of adjacent digits. Use the enumerate function to keep track of the index, and pairwise from the itertools module to conveniently work with pairs.
Parity Check: For each pair of adjacent digits, check if they have the same parity. Parity can be checked using the modulo operation: digits a and b have the same parity if (a + b) % 2 == 0.
Lexicographical Order Check: If both digits have the same parity, determine if the preceding digit (a) is greater than the succeeding digit (b). This can be done by comparing their ASCII values using map(ord, s).
Swap and Return: If conditions are met (same parity and a > b), swap these two digits to obtain a smaller string. Construct the new string with the swapped digits using slicing: append the swapped pair s[i + 1] + s[i] between segments s[:i] and s[i + 2:].
Completion: If no swap is possible or beneficial upon traversing the string, return the original string as it's already in its smallest order.

This approach ensures that a swap only occurs when it strictly improves the order of the string, and only a single swap is allowed. The algorithm efficiently makes an optimal decision at the first opportunity detected during the traversal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the string s = "4321". Our goal is to find the lexicographically smallest string that can be obtained after swapping adjacent digits with the same parity, at most once.

Initial String: Start with the string s = "4321".
First Pair (Index 0 and 1):
- Digits are 4 and 3.
- Parity check: 4 is even and 3 is odd, so they have different parities.
- No swap is possible.
Second Pair (Index 1 and 2):
- Digits are 3 and 2.
- Parity check: 3 is odd and 2 is even, so they have different parities.
- No swap is possible.
Third Pair (Index 2 and 3):
- Digits are 2 and 1.
- Parity check: 2 is even and 1 is odd, so they have different parities.
- No swap is possible.
Completion: After traversing the entire string, no adjacent digits with the same parity are found that can be swapped to make the string smaller. Thus, the original string s = "4321" is already in its smallest possible order for the given conditions.

Therefore, the output is "4321".

Solution Implementation

1from itertools import pairwise
2
3class Solution:
4    def getSmallestString(self, s: str) -> str:
5        # Iterate through pairwise combinations of character ASCII codes
6        for i, (a, b) in enumerate(pairwise(map(ord, s))):
7            # Check if the sum of ASCII values is even and the first value is greater
8            if (a + b) % 2 == 0 and a > b:
9                # Swap the current character with the next character and return the modified string
10                return s[:i] + s[i + 1] + s[i] + s[i + 2:]
11      
12        # Return the original string if no swaps are performed
13        return s
14

1class Solution {
2    public String getSmallestString(String s) {
3        // Convert the string to a character array for easy manipulation
4        char[] charArray = s.toCharArray();
5        int length = charArray.length;
6
7        // Iterate through the character array starting from the second character
8        for (int i = 1; i < length; ++i) {
9            char previousChar = charArray[i - 1];
10            char currentChar = charArray[i];
11
12            // Check if the previous character is greater than the current character
13            // and both characters have the same parity (either both even or both odd)
14            if (previousChar > currentChar && previousChar % 2 == currentChar % 2) {
15                // Swap the characters to get a lexicographically smaller string
16                charArray[i] = previousChar;
17                charArray[i - 1] = currentChar;
18              
19                // Return the new string
20                return new String(charArray);
21            }
22        }
23      
24        // If no swap was made, return the original string
25        return s;
26    }
27}
28

1class Solution {
2public:
3    // Function to return the lexicographically smallest string
4    // by swapping adjacent characters once
5    string getSmallestString(string s) {
6        int length = s.length();  // Get the length of the input string
7        // Traverse the string to find a pair of characters to swap
8        for (int i = 1; i < length; ++i) {
9            char previousChar = s[i - 1];  // Get the previous character
10            char currentChar = s[i];       // Get the current character
11            // Check if previous character is greater than the current and
12            // both are either even or odd alphabetically
13            if (previousChar > currentChar && previousChar % 2 == currentChar % 2) {
14                s[i - 1] = currentChar;  // Swap the characters
15                s[i] = previousChar;
16                break;  // Only one swap is allowed, so break the loop
17            }
18        }
19        return s;  // Return the modified string
20    }
21};
22

1// This function takes a string 's' as input and returns a new string
2// that is the lexicographically smallest possible by swapping adjacent 
3// characters, given certain conditions.
4function getSmallestString(s: string): string {
5    const n = s.length; // Determine the length of the string.
6    const cs: string[] = s.split(''); // Convert the string into an array of characters.
7
8    // Iterate through each character starting from the second one.
9    for (let i = 1; i < n; ++i) {
10        const prevChar = cs[i - 1]; // Get the previous character.
11        const currentChar = cs[i];  // Get the current character.
12
13        // Check if the previous character is greater than the current character 
14        // and both characters have the same even or odd parity.
15        if (prevChar > currentChar && +prevChar % 2 === +currentChar % 2) {
16            // Swap the previous and current characters.
17            cs[i - 1] = currentChar;
18            cs[i] = prevChar;
19
20            // Join the array back into a string and return.
21            return cs.join('');
22        }
23    }
24    // If no swaps are made, return the original string.
25    return s;
26}
27

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the string s. This is because the code involves iterating through the string once to perform the swapping check, which results in a linear time complexity.

The space complexity is also O(n) because creating a new string with slicing and concatenation involves allocating space proportional to the length of the string s.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: