Dare2Solve
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.
s
into a list of characters to facilitate swapping.s
. This is because we only pass through the string a constant number of times.s
and the resultant string.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;
}
};
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)
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);
}
}
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("");
};