【Leetcode】1433. Check If a String Can Break Another String（配数学证明）_letcode 1433

题目地址：

https://leetcode.com/problems/check-if-a-string-can-break-another-string/

给定两个等长字符串$s_1$和$s_2$，长都为$n$。问是否存在$s_1$的某个排列$s_1^{\prime }$和$s_2$的某个排列$s_2^{\prime }$使得$\forall i,s_1^{\prime }[i]\le s_2^{\prime }[i]$或者$\forall i,s_1^{\prime }[i]\ge s_2^{\prime }[i]$。题目保证只含英文小写字母。

开两个长$26$的数组，分别数一下两个字符串里每个字母出现多少次。接着从'a'遍历到'z'，使用“消去”的办法，每次都消去等量的字母，同时记录$s_1$里的字母小还是大。最后如果同时出现过“小”和”大“，则说明不存在，否则说明存在。这其实等价于直接比较$s_1$按字典序排序后的数组与$s_2$按字典序排序后的数组，实质是贪心的思想，证明可以采用调整法，如果存在某个排列使得$\forall i,s_1^{\prime }[i]\le s_2^{\prime }[i]$，先对$s_1$按字典序排序，若$s_1^{\prime }[n-1]$与$s_2^{\prime }[k]$时有解，若$k\ne n-1$，则可以直接将$s_2^{\prime }[k]$和$s_2^{\prime }[n-1]$进行调换，这样也是满足条件的；然后向前遍历，逐步调换，就可以将$s_2$也调整成字典序，从而说明两者都是字典序的情况下也会有$\forall i,s_1^{\prime }[i]\le s_2^{\prime }[i]$，从而证明了结论。

代码如下：

public class Solution {
    public boolean checkIfCanBreak(String s1, String s2) {
        int[] cnt1 = new int[26], cnt2 = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            cnt1[s1.charAt(i) - 'a']++;
            cnt2[s2.charAt(i) - 'a']++;
        }
        
        boolean smaller = false, greater = false;
        for (int i = 0, j = 0; ; ) {
            while (i < 26 && cnt1[i] == 0) {
                i++;
            }
            while (j < 26 && cnt2[j] == 0) {
                j++;
            }
            if (i == 26 || j == 26) {
                break;
            }
            
            int min = Math.min(cnt1[i], cnt2[j]);
            cnt1[i] -= min;
            cnt2[j] -= min;
            
            if (i < j) {
                smaller = true;
            } else if (i > j) {
                greater = true;
            }
        }
        
        return !(smaller && greater);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

时间复杂度$O(n)$，空间$O(1)$。