🎨Now live: Try our Free AI Image Generation Feature

Intuition
To find the lexicographically smallest string after allowed swaps, we need to carefully consider which adjacent pairs to swap to achieve the smallest possible order.
Approach
- Convert the String: Convert the string
s
into a list of characters to facilitate swapping. - Iterate and Swap: Traverse through the list and swap adjacent digits if they have the same parity and the first digit is larger than the second.
- Return the Result: Convert the list back to a string and return it as the result.
Complexity
- Time Complexity: O(n), where n is the length of the string
s
. This is because we only pass through the string a constant number of times. - Space Complexity: O(n) due to the storage of the list of characters from string
s
and the resultant string.
Code
C++
class Solution {
public:
string getSmallestString(string s) {
for (int i = 1; i < s.length(); ++i) {
if ((s[i - 1] & 1) == (s[i] & 1) && s[i - 1] > s[i]) {
swap(s[i], s[i - 1]);
break;
}
}
return s;
}
};
Python
class Solution:
def getSmallestString(self, s: str) -> str:
arr = list(s)
for i in range(1, len(arr)):
if (int(arr[i - 1]) & 1 == int(arr[i]) & 1) and int(arr[i - 1]) > int(arr[i]):
arr[i], arr[i - 1] = arr[i - 1], arr[i]
break
return "".join(arr)
Java
class Solution {
public String getSmallestString(String s) {
char[] arr = s.toCharArray();
for (int i = 1; i < arr.length; ++i) {
if ((arr[i - 1] & 1) == (arr[i] & 1) && arr[i - 1] > arr[i]) {
char temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
break;
}
}
return new String(arr);
}
}
JavaScript
var getSmallestString = function (s) {
var arr = s.split("").map(Number);
for (var i = 1; i < arr.length; ++i) {
if ((arr[i - 1] & 1) === (arr[i] & 1) && arr[i - 1] > arr[i]) {
[arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
break;
}
}
return arr.join("");
};