题目描述

给你两个字符串 s1 和 s2，它们长度相等，请你检查是否存在一个 s1 的排列可以打破 s2 的一个排列，或者是否存在一个 s2 的排列可以打破 s1 的一个排列。

字符串 x 可以打破字符串 y（两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。

样例

输入：s1 = "abc", s2 = "xya"
输出：true
解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，
且 "ayx" 可以打破 "abc"。

输入：s1 = "abe", s2 = "acd"
输出：false 
解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba"；
s2="acd" 的所有排列包括："acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。
然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。

输入：s1 = "leetcodee", s2 = "interview"
输出：true

限制

• s1.length == n
• s2.length == n
• 1 <= n <= 10^5
• 所有字符串都只包含小写英文字母。

算法

(贪心排序) $O(n + 26)$

1. 可以很容易的想到如果两个字符串都是排好序的，则可以直接在线性时间内判断答案。可以通过“贪心交换仍然是最优的”方式来证明。
2. 因为字符集只有小写英文字母，所以可以考虑使用计数排序。

时间复杂度

• 计数排序的时间复杂度为 $O(n + 26)$。

空间复杂度

• 需要额外 26 的空间。

C++ 代码

class Solution {
public:
    void csort(string &s) {
        int n = s.size();
        vector<int> c(26, 0);
        for (int i = 0; i < n; i++)
            c[s[i] - 'a']++;

        for (int i = 25; i >= 0; i--)
            while (c[i]--)
                s[--n] = i + 'a';
    }

    bool checkIfCanBreak(string s1, string s2) {
        csort(s1);
        csort(s2);

        int n = s1.size();
        bool f1 = true, f2 = true;
        for (int i = 0; i < n; i++)
            if (s1[i] < s2[i]) f1 = false;
            else if (s1[i] > s2[i]) f2 = false;

        return f1 || f2;
    }
};