我们已经给定了两个字符串，需要检查给定字符串的排列是否存在，以便一个排列可以比第 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 <algorithm>
#include <iostream>
#include <string>
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 <iostream>
#include <string>
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)，因为我们在数组中存储字符的频率。

我们学会了检查两个字符串是否存在任何排列，使得一个字符串的所有字符都可以大于另一个字符串。第一种方法采用排序方法，第二种方法采用字符累积频率。