3216. Lexicographically Smallest String After a Swap LeetCode Solution
In this guide, you will get 3216. Lexicographically Smallest String After a Swap LeetCode Solution with the best time and space complexity. The solution to Lexicographically Smallest String After a Swap problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Lexicographically Smallest String After a Swap
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3216. Lexicographically Smallest String After a Swap LeetCode Solution in C++
class Solution {
public:
string getSmallestString(string s) {
for (int i = 1; i < s.length(); ++i)
if (s[i - 1] % 2 == s[i] % 2 && s[i - 1] > s[i]) {
swap(s[i - 1], s[i]);
break;
}
return s;
}
}; /* code provided by PROGIEZ */
3216. Lexicographically Smallest String After a Swap LeetCode Solution in Java
class Solution {
public String getSmallestString(String s) {
char[] chars = s.toCharArray();
for (int i = 1; i < chars.length; ++i) {
if (chars[i - 1] % 2 == chars[i] % 2 && chars[i - 1] > chars[i]) {
final char temp = chars[i - 1];
chars[i - 1] = chars[i];
chars[i] = temp;
return new String(chars);
}
}
return s;
}
} // code provided by PROGIEZ
3216. Lexicographically Smallest String After a Swap LeetCode Solution in Python
class Solution:
def getSmallestString(self, s: str) -> str:
chars = list(s)
for i, (a, b) in enumerate(itertools.pairwise(chars)):
if ord(a) % 2 == ord(b) % 2 and a > b:
chars[i], chars[i + 1] = chars[i + 1], chars[i]
return ''.join(chars)
return s # code by PROGIEZ
