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.
交换后字典序最小的字符串。
给你一个仅由数字组成的字符串 s，在最多交换一次 相邻 且具有相同 奇偶性 的数字后，返回可以得到的字典序最小的字符串。如果两个数字都是奇数或都是偶数，则它们具有相同的奇偶性。例如，5 和 9、2 和 4 奇偶性相同，而 6 和 9 奇偶性不同。
思路
注意交换的规则，两个数字只能同为奇数或者同为偶数才能互相交换。所以思路是从左往右遍历所有的字符，如果某两个相邻的字符 a 和 b (a 在左，b 在右) 具有相同的奇偶性且 a > b，则可以进行交换。照着这个思路，找到第一对符合条件的 a 和 b，即可交换并返回结果。为什么是第一对，是因为需要让字典序尽可能的小，你交换在后面的字符，字典序是不如交换第一对大的。
复杂度
时间O(n)
空间O(n)
代码
Java实现
class Solution {
public String getSmallestString(String s) {
int n = s.length();
char[] letters = s.toCharArray();
for (int i = 1; i < n; i++) {
int a = letters[i - 1] - '0';
int b = letters[i] - '0';
if (helper(a, b) && a > b) {
char temp = letters[i - 1];
letters[i - 1] = letters[i];
letters[i] = temp;
return new String(letters);
}
}
return s;
}
private boolean helper(int a, int b) {
return a % 2 == b % 2;
}
}