我们已经给定了两个字符串，需要检查给定字符串的排列是否存在，以便一个排列可以比第 i 个索引处的另一个排列具有更大的字符。
我们可以通过对字符串进行排序，并逐一比较字符串中的每个字符来解决问题。另外，我们可以利用两个字符串的字符频率来解决问题。
问题陈述 - 我们给出了长度为N的字符串str1和str2。我们需要检查是否存在任何字符串的排列，使得其中一个字符串的排列在字典序上大于另一个字符串。这意味着任何排列都应该在第i个索引处具有比另一个字符串排列的第i个索引字符更大的字符。
示例
输入 - str1 = "aef"; str2 = "fgh";
输出– 是
解释– ‘fgh’ 已经大于 ‘aef’。在这里，a > f, g > e, h > f。
输入– str1 = "adsm"; str2 = "obpc";
输出– 否
Explanation– 我们无法找到任何一种排列，使得其中一个字符串的每个字符都大于另一个排列。
方法 1
在这种方法中，我们将按字典顺序对两个字符串进行排序。然后，我们将比较字符串的每个字符。如果str1的所有字符都小于str2，或者str2的所有字符都小于str1，则返回true。否则，返回false。
算法
使用 sort() 方法对字符串进行排序。
定义 isStr1Greater 布尔变量并使用 true 进行初始化。
遍历字符串，并且如果str1中第i个索引位置的字符小于str2，将isStr1Greater的值更新为false，并使用break关键字中断循环
如果 isStr1Greater 为真，则循环成功完成并返回真。
现在，遍历字符串以检查 str2 是否大于 str1。如果我们发现 str1 的任何字符都大于 str2，则返回 false。
如果循环成功完成，则返回true。
示例
#include#include #include using namespace std; bool isAnyPermLarge(string string1, string string2) { // sort the strings sort(string1.begin(), string1.end()); sort(string2.begin(), string2.end()); // to keep track if string1 is greater than string2 bool isStr1Greater = true; // traverse the string for (int i = 0; i < string1.length(); i++) { // if any character of string1 is less than string2, return false. if (string1[i] < string2[i]) { isStr1Greater = false; break; } } // If string1 is greater, returning true if (isStr1Greater) return true; // traverse the string for (int i = 0; i < string2.length(); i++) { // if any character of string2 is less than string1, return false. if (string1[i] > string2[i]) { return false; } } // return true if string2 is greater than string1 return true; } int main() { string string1 = "aef"; string string2 = "fgh"; bool res = isAnyPermLarge(string1, string2); if (res) { cout << "Yes, permutation exists such that one string is greater than the other."; } else { cout << "No, permutation does not exist such that one string is greater than the other."; } return 0; }
输出
Yes, permutation exists such that one string is greater than the other.
时间复杂度 - O(N*logN)，因为我们对字符串进行排序。
空间复杂度 - O(N) 是用来对字符串进行排序所需的。
方法2
在这种方法中，我们将存储两个字符串中每个字符的总频率。之后，我们将使用累积频率来决定是否可以找到任何字符串排列，使得其中一个大于另一个。
算法
定义长度为26的map1和map2数组，并初始化为零。
将str1中字符的频率存储到map1中，将str2中字符的频率存储到map2中。
定义isStr1和isStr2布尔变量，并初始化为false，以跟踪str1是否大于str2。
定义cnt1和cnt2变量来存储字符串字符的累积频率。
遍历map1和map2。将map1[i]添加到cnt1，将map2[i]添加到cnt2。
如果 cnt1 大于 cnt2，则 str1 到第 i 个索引处的字符的累积频率更大。如果是这样，并且 str2 已经更大，则返回 false。否则，将 isStr1 更改为 true
如果 cnt2 大于 cnt1，则 str2 中第 i 个索引处字符的累积频率更大。如果是这样，并且 str1 已经更大，则返回 false。否则，将 isStr2 更改为 true
最后返回true。
示例
#include#include using namespace std; bool isAnyPermLarge(string string1, string string2) { int map1[26] = {0}; int map2[26] = {0}; // store the frequency of each character in the map1 for (int i = 0; i < string1.length(); i++) { map1[string1[i] - 'a']++; } // store the frequency of each character in the map2 for (int i = 0; i < string2.length(); i++) { map2[string2[i] - 'a']++; } // To keep track of which string is smaller. Initially, both strings are equal. bool isStr1 = false, isStr2 = false; // to count the cumulative frequency of characters of both strings int cnt1 = 0, cnt2 = 0; // traverse for all characters. for (int i = 0; i < 26; i++) { // update the cumulative frequency of characters cnt1 += map1[i]; cnt2 += map2[i]; if (cnt1 > cnt2) { // If string2 is already greater and cumulative frequency of string1 is greater than string2, then return false if (isStr2) return false; // update isStr1 to true as string1 is smaller isStr1 = true; } if (cnt1 < cnt2) { // If string1 is already greater and cumulative frequency of string2 is greater than string1, then return false if (isStr1) return false; // update isStr2 to true as string2 is smaller isStr2 = true; } } return true; } int main() { string string1 = "aef"; string string2 = "fgh"; bool res = isAnyPermLarge(string1, string2); if (res) { cout << "Yes, permutation exists such that one string is greater than the other."; } else { cout << "No, permutation does not exist such that one string is greater than the other."; } return 0; }
输出
Yes, permutation exists such that one string is greater than the other.
时间复杂度 - O(N)，因为我们计算字符的频率。
空间复杂度 - O(26)，因为我们在数组中存储字符的频率。
我们学会了检查两个字符串是否存在任何排列，使得一个字符串的所有字符都可以大于另一个字符串。第一种方法采用排序方法，第二种方法采用字符累积频率。
