检查给定字符串的任何排列是否按字典序大于另一个给定字符串

---

我们给出了两个字符串，需要检查是否存在给定字符串的排列，使得一个排列在第 i 个索引处的字符大于另一个排列。

我们可以通过对字符串进行排序并逐个比较字符串的每个字符来解决问题。此外，我们还可以使用两个字符串的字符频率来解决问题。

问题陈述 – 我们给定两个长度为 N 的字符串 str1 和 str2。我们需要检查是否存在这两个字符串的任何排列，使得一个字符串的排列按字典序大于另一个字符串。这意味着任何排列都应该在第 i 个索引处具有比另一个字符串排列的第 i 个索引处的字符更大的字符。

示例

输入 – str1 = "aef"; str2 = "fgh";

输出– 是

说明– “fgh” 已经大于 “aef”。这里，a > f, g > e, h > f。

输入 – str1 = "adsm"; str2 = "obpc";

输出– 否

说明– 我们无法找到这两个字符串的任何排列，使得一个字符串的每个字符都大于另一个排列。

方法 1

在这种方法中，我们将对这两个字符串进行按字典序排序。然后，我们将比较字符串的每个字符。如果 str1 的所有字符都小于 str2，或者 str2 的所有字符都小于 str1，则返回 true。否则，我们返回 false。

算法

• 使用 sort() 方法对字符串进行排序。

• 定义布尔变量 isStr1Greater 并初始化为 true。

• 遍历字符串，如果 str1 中第 i 个索引处的任何字符小于 str2，则将 isStr1Greater 的值更新为 false，并使用 break 关键字退出循环

• 如果 isStr1Greater 为 true，则循环成功完成并返回 true。

• 现在，遍历字符串以检查 str2 是否大于 str1。如果我们发现 str1 的任何字符更大，则返回 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)，因为我们将字符的频率存储在数组中。

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