# Lexicographically Smallest String After a Swap
**Difficulty:** EASY
[External](https://leetcode.com/problems/lexicographically-smallest-string-after-a-swap)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-string-after-a-swap
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
Given a string `s` containing only digits, 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, 5 and 9, as well as 2 and 4, have the same parity, while 6 and 9 do not.

**Example 1:**

**Input:** s = "45320"

**Output:** "43520"

**Explanation:** 

`s[1] == '5'` and `s[2] == '3'` both have the same parity, and swapping them results in the lexicographically smallest string.

**Example 2:**

**Input:** s = "001"

**Output:** "001"

**Explanation:**

There is no need to perform a swap because `s` is already the lexicographically smallest.

**Constraints:**

* `2 <= s.length <= 100`
* `s` consists only of digits.

# Approaches
## Brute Force: Generate and Compare All Swaps
This approach systematically generates every possible string that can be created by performing a single valid swap. It then compares all these generated strings, along with the original string, to find the one that is lexicographically smallest.
**Time:** O(N^2), where N is the length of the string. The main loop runs N-1 times. Inside the loop, creating a new string from a character array takes O(N) time, and comparing two strings also takes O(N) time. This leads to a total complexity of O(N * N). · **Space:** O(N), where N is the length of the string. A character array of size N is used, and for each potential swap, a new temporary string and character array of size N are created.
**Pros:** Simple to understand and implement.; Guarantees the correct answer by exhaustively checking all possibilities.
**Cons:** Inefficient due to its O(N^2) time complexity, which can be slow for larger inputs (though acceptable for the given constraints).; Performs redundant work by checking all possible swaps, even after finding a swap that results in a lexicographically smaller string.
### Explanation
The algorithm initializes a variable, say `smallestString`, with the original string `s`. It then iterates through all adjacent pairs of characters in the string, from index `i = 0` to `n-2`, where `n` is the length of the string. For each pair `(s[i], s[i+1])`, it checks if the two digits have the same parity (both even or both odd). If they do, it creates a new temporary string by swapping these two characters. This new string is then lexicographically compared with the current `smallestString`. If the new string is smaller, `smallestString` is updated. After checking all possible adjacent pairs, the final `smallestString` holds the lexicographically smallest possible string after at most one swap, which is then returned. This method is exhaustive but less efficient because it continues to search for swaps even after a potentially optimal one has been found.

```java
class Solution {
    public String smallestString(String s) {
        String smallestString = s;
        char[] chars = s.toCharArray();
        int n = s.length();

        for (int i = 0; i < n - 1; i++) {
            int d1 = chars[i] - '0';
            int d2 = chars[i + 1] - '0';

            if ((d1 % 2) == (d2 % 2)) {
                // Create a temporary copy and perform the swap
                char[] tempChars = s.toCharArray();
                char temp = tempChars[i];
                tempChars[i] = tempChars[i + 1];
                tempChars[i + 1] = temp;
                
                String tempString = new String(tempChars);
                
                // Update the smallest string found so far
                if (tempString.compareTo(smallestString) < 0) {
                    smallestString = tempString;
                }
            }
        }
        return smallestString;
    }
}
```
### Algorithm
- Initialize a string variable `smallestString` with the original string `s`.
- Iterate through the string from `i = 0` to `s.length() - 2`.
- For each index `i`, check if the digits at `s[i]` and `s[i+1]` have the same parity.
- If they do, create a new temporary string `tempString` by swapping the characters at `i` and `i+1`.
- Compare `tempString` with `smallestString`. If `tempString` is lexicographically smaller, update `smallestString` to `tempString`.
- After the loop finishes, return `smallestString`.

## Single Pass Greedy Approach
A more efficient approach is to use a greedy strategy. To make a string lexicographically smallest, we want to make the earliest possible character smaller. We can achieve this by finding the first position `i` where a swap of `s[i]` and `s[i+1]` would result in a smaller character at `s[i]`. Once we find and perform this swap, any subsequent swap would affect a later position, resulting in a lexicographically larger string. Therefore, the first beneficial swap we find is the optimal one.
**Time:** O(N), where N is the length of the string. The algorithm iterates through the string at most once. If a swap is performed, creating the new string takes O(N) time, and the function returns. In the worst case (no swap), the loop runs N-1 times with constant time operations in each iteration. · **Space:** O(N). A character array of size N is created to hold the characters of the string. This is necessary because strings are immutable in Java.
**Pros:** Highly efficient with a linear time complexity of O(N).; Simple and elegant logic that finds the optimal solution in a single pass.
**Cons:** The greedy logic, while simple, might not be immediately obvious without understanding the properties of lexicographical ordering.
### Explanation
The algorithm iterates through the string from left to right, examining adjacent characters `s[i]` and `s[i+1]`. For each pair, it checks two conditions: 1. Do `s[i]` and `s[i+1]` have the same parity? 2. Is `s[i]` greater than `s[i+1]`? If both conditions are true, it means swapping them will place a smaller digit at index `i`, making the entire string lexicographically smaller. Since we are iterating from left to right, the first time we find such a pair is the leftmost (and thus most significant) position where we can improve the string. Upon finding this pair, the algorithm performs the swap and immediately returns the new string. If the loop completes without finding any such pair, it implies that no single adjacent swap can make the string smaller. In this case, the original string is already the smallest possible, and it is returned unchanged.

```java
class Solution {
    public String smallestString(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();

        for (int i = 0; i < n - 1; i++) {
            // Get the integer values of the characters
            int d1 = chars[i] - '0';
            int d2 = chars[i + 1] - '0';

            // Check for same parity
            if ((d1 % 2) == (d2 % 2)) {
                // Check if swapping makes the string lexicographically smaller
                if (d1 > d2) {
                    // Swap the characters
                    char temp = chars[i];
                    chars[i] = chars[i + 1];
                    chars[i + 1] = temp;
                    
                    // Return the new string immediately as this is the best possible swap
                    return new String(chars);
                }
            }
        }
        
        // If no swap was made, return the original string
        return s;
    }
}
```
### Algorithm
- Convert the input string `s` to a character array `chars` for easy modification.
- Loop `i` from `0` to `s.length() - 2`.
- Get the integer values of the digits at `chars[i]` and `chars[i+1]`.
- Check if they have the same parity AND if the digit at `i` is greater than the digit at `i+1`.
- If both conditions are true, this is the first and best opportunity for a swap.
- Swap `chars[i]` and `chars[i+1]`.
- Return the new string created from the modified `chars` array immediately.
- If the loop completes without finding any such pair, it means no beneficial swap is possible. Return the original string `s`.

# Solutions
### Java

```java
class Solution {
public
  String getSmallestString(String s) {
    char[] cs = s.toCharArray();
    int n = cs.length;
    for (int i = 1; i < n; ++i) {
      char a = cs[i - 1], b = cs[i];
      if (a > b && a % 2 == b % 2) {
        cs[i] = a;
        cs[i - 1] = b;
        return new String(cs);
      }
    }
    return s;
  }
}

```

### CPP

```cpp
class Solution {
public:
  string getSmallestString(string s) {
    int n = s.length();
    for (int i = 1; i < n; ++i) {
      char a = s[i - 1], b = s[i];
      if (a > b && a % 2 == b % 2) {
        s[i - 1] = b;
        s[i] = a;
        break;
      }
    }
    return s;
  }
};

```

### Python

```python
class Solution:
    def getSmallestString(self, s: str) -> str: for i, (a, b) in enumerate(pairwise(map(ord, s))): if (a + b) % 2 == 0 and a > b: return s[: i] + s[i + 1] + s[i] + s[i + 2:] return s

```