排序题目：检查一个字符串是否可以打破另一个字符串

题目

标题和出处

标题：检查一个字符串是否可以打破另一个字符串

出处：1433. 检查一个字符串是否可以打破另一个字符串

难度

4 级

题目描述

要求

给定两个长度相等的字符串 $\text{s1}$ 和 $\text{s2}$，检查是否存在一个 $\text{s1}$ 的排列可以打破 $\text{s2}$ 的一个排列，或者是否存在一个 $\text{s2}$ 的排列可以打破 $\text{s1}$ 的一个排列。

字符串 $\text{x}$ 可以打破字符串 $\text{y}$（两者长度都为 $\text{n}$）需满足对于所有 $\text{0}\le \text{i}<\text{n}$ 都有 $\text{x[i]}\ge \text{y[i]}$（字典序意义下的顺序）。

示例

示例 1：

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

示例 2：

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

示例 3：

输入：$\text{s1 = "leetcodee", s2 = "interview"}$
输出：$\text{true}$

数据范围

• $\text{s1.length}=\text{n}$
• $\text{s2.length}=\text{n}$
• $\text{1}\le \text{n}\le {\text{10}}^{\text{5}}$
• 所有字符串都只包含小写英语字母

解法

思路和算法

对于长度为 $n$ 的两个字符串 $s_1$ 和 $s_2$，假设存在 $s_1$ 和 $s_2$ 的排列使得 $s_1$ 的排列可以打破 $s_2$ 的排列或者 $s_2$ 的排列可以打破 $s_1$ 的排列，则将字符串 $s_1$ 和 $s_2$ 分别升序排序之后得到的两个排列之间一定存在打破的关系。

将字符串 $s_1$ 和 $s_2$ 分别升序排序，用 $t_1$ 和 $t_2$ 分别表示 $s_1$ 和 $s_2$ 升序排序之后的结果。排序之后，对于每个 $0\le i<n$，比较 $t_1[i]$ 和 $t_2[i]$ 的大小，并判断可能的打破关系。

• 如果 $t_1[i]=t_2[i]$，则根据下标 $i$ 处的字母判断，可能是 $t_1$ 打破 $t_2$ 或者 $t_2$ 打破 $t_1$。

• 如果 $t_1[i]>t_2[i]$，则根据下标 $i$ 处的字母判断，只可能是 $t_1$ 打破 $t_2$。

• 如果 $t_1[i]<t_2[i]$，则根据下标 $i$ 处的字母判断，只可能是 $t_2$ 打破 $t_1$。

因此如果存在两个不同的下标 $j$ 和 $k$ 使得 $t_1[j]>t_2[j]$ 和 $t_1[k]<t_2[k]$，则不存在 $s_1$ 和 $s_2$ 的排列使得一个字符串的排列可以打破另一个字符串的排列。

将字符串 $s_1$ 和 $s_2$ 升序排序之后，判断两个字符串的排列是否存在打破关系的方法是：同时遍历两个排序后的字符串 $t_1$ 和 $t_2$，统计 $t_1$ 的字符大于 $t_2$ 的字符的下标个数 $\text{greater}$ 以及 $t_1$ 的字符小于 $t_2$ 的字符的下标个数 $\text{less}$。遍历结束之后，根据 $\text{greater}$ 和 $\text{less}$ 的值判断两个字符串的排列是否存在打破关系。

• 如果 $\text{greater}$ 和 $\text{less}$ 中至少有一个为 $0$，则两个字符串的排列存在打破关系。

• 如果 $\text{greater}$ 和 $\text{less}$ 都大于 $0$，则两个字符串的排列不存在打破关系。

实现方面，由于 Java 中的 $\text{String}$ 类型的对象是不可变的，因此需要对 $s_1$ 和 $s_2$ 分别调用 $\text{toCharArray}$ 方法得到 $\text{char}$ 类型的数组，然后对两个字符数组排序。

证明

将字符串 $s_1$ 和 $s_2$ 分别升序排序之后，如果两个有序字符串之间存在打破关系，由于两个有序字符串分别是 $s_1$ 和 $s_2$ 的排列，因此存在 $s_1$ 和 $s_2$ 使得打破关系成立。

如果两个有序字符串之间不存在打破关系，则两个字符串的任意排列之间都不存在打破关系。证明如下。

如果两个有序字符串之间不存在打破关系，则存在两个不同的下标 $j$ 和 $k$ 使得 $t_1[j]>t_2[j]$ 和 $t_1[k]<t_2[k]$。以下考虑 $j<k$ 的情况，使用相同的思路也可以证明 $j>k$ 的情况。

• 假设存在大于 $k$ 的下标 $k^{\prime }$ 使得 $t_1[k^{\prime }]\ge t_2[k]$，将 $t_1[k]$ 和 $t_1[k^{\prime }]$ 的两个字符交换之后有 $t_1[k]\ge t_2[k]$。在交换 $t_1$ 的两个字符之后，一定有 $t_1[k^{\prime }]<t_2[k^{\prime }]$，由于 $t_2[k^{\prime }]\ge t_2[k]$。因此 $t_1$ 的最大的 $n-k$ 个字符不可能同时大于等于 $t_2$ 的最大的 $n-k$ 个字符（对应下标）。

• 假设存在小于 $j$ 的下标 $j^{\prime }$ 使得 $t_1[j^{\prime }]\le t_2[j]$，将 $t_1[j]$ 和 $t_1[j^{\prime }]$ 的两个字符交换之后有 $t_1[j]\le t_2[j]$。在交换 $t_1$ 的两个字符之后，一定有 $t_1[j^{\prime }]>t_2[j^{\prime }]$，由于 $t_2[j^{\prime }]\le t_2[j]$。因此 $t_1$ 的最小的 $j+1$ 个字符不可能同时小于等于 $t_2$ 的最小的 $j+1$ 个字符（对应下标）。

因此如果两个有序字符串之间不存在打破关系，则两个字符串的任意排列之间都不存在打破关系。

代码

class Solution {public boolean checkIfCanBreak(String s1, String s2) {int n = s1.length();char[] arr1 = s1.toCharArray();char[] arr2 = s2.toCharArray();Arrays.sort(arr1);Arrays.sort(arr2);int greater = 0, less = 0;for (int i = 0; i < n; i++) {if (arr1[i] > arr2[i]) {greater++;} else if (arr1[i] < arr2[i]) {less++;}}return greater == 0 || less == 0;}
}

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 是字符串 $s_1$ 和 $s_2$ 的长度。需要 $O(n\log n)$ 的时间对两个字符数组排序，排序后需要 $O(n)$ 的时间比较两个字符数组的相同位置字符，因此时间复杂度是 $O(n\log n)$。

• 空间复杂度：$O(n)$，其中 $n$ 是字符串 $s_1$ 和 $s_2$ 的长度。需要创建两个长度为 $n$ 的字符数组，排序需要 $O(\log n)$ 的递归调用栈空间，因此空间复杂度是 $O(n)$。