Leetcode3216. 交换后字典序最小的字符串

Every day a Leetcode

题目来源：3216. 交换后字典序最小的字符串

解法1：模拟

找到第一个 s[i] > s[i + 1]，且它们奇偶性相同，交换它们。

代码：

/** @lc app=leetcode.cn id=3216 lang=cpp** [3216] 交换后字典序最小的字符串*/// @lc code=start
class Solution
{
public:string getSmallestString(string s){int n = s.size();for (int i = 0; i < n - 1; i++){if (s[i] > s[i + 1] && check(s[i] - '0', s[i + 1] - '0')){swap(s[i], s[i + 1]);return s;}}return s;}// 辅函数bool check(int a, int b){return a % 2 == b % 2;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(1)。