Checks whether any permutation of a given string is lexicographically greater than another given string

We have been given two strings and need to check if a permutation of the given string exists so that one permutation can have a greater value than the other permutation at the i-th index character of.

We can solve the problem by sorting the string and comparing each character in the string one by one. Alternatively, we can use the character frequencies of the two strings to solve the problem.

Problem Statement - We are given strings str1 and str2 of length N. We need to check if there are any permutations of strings such that one is lexicographically greater than the other. This means that any permutation should have a character at the i-th index that is greater than the character at the i-th index of another string permutation.

Example

Input - str1 = "aef"; str2 = "fgh";

Output–Yes

Explanation– ‘fgh’ is already larger than ‘aef’. Here, a > f, g > e, h > f.

Input– str1 = "adsm"; str2 = "obpc";

Output–No

Explanation– We cannot find any arrangement in which every character of one string is larger than the other.

method 1

In this method, we will sort two strings in lexicographic order. We will then compare each character of the string. Returns true if all characters of str1 are less than str2, or if all characters of str2 are less than str1. Otherwise, return false.

algorithm

• Use the sort() method to sort strings.

• Define the isStr1Greater Boolean variable and initialize it with true.

• Traverse the string, and if the character at the i-th index position in str1 is less than str2, update the value of isStr1Greater to false, and use the break keyword to interrupt the loop

• If isStr1Greater is true, the loop completes successfully and returns true.

• Now, iterate over the string to check if str2 is greater than str1. If we find any character of str1 greater than str2, then return false.

• Returns true if the loop completes successfully.

Example

#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;
}

Output

Yes, permutation exists such that one string is greater than the other.

Time complexity - O(N*logN), because we sort the strings.

Space Complexity - O(N) is required to sort the strings.

Method 2

In this method we will store the total frequency of each character in both strings. Afterwards, we will use the cumulative frequencies to decide if we can find any permutations of strings such that one is greater than the other.

algorithm

• Define map1 and map2 arrays with a length of 26 and initialize them to zero.

• Store the frequency of characters in str1 into map1, and store the frequency of characters in str2 into map2.

• Define isStr1 and isStr2 Boolean variables and initialize them to false to track whether str1 is greater than str2.

• Define cnt1 and cnt2 variables to store the cumulative frequency of string characters.

• Traverse map1 and map2. Add map1[i] to cnt1 and map2[i] to cnt2.

• If cnt1 is greater than cnt2, the cumulative frequency of characters from str1 to the i-th index is greater. If so, and str2 is already larger, return false. Otherwise, change isStr1 to true

• If cnt2 is greater than cnt1, the cumulative frequency of the character at the i-th index in str2 is greater. If so, and str1 is already larger, return false. Otherwise, change isStr2 to true

• Finally returns true.

Example

#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;
}

Output

Yes, permutation exists such that one string is greater than the other.

Time complexity - O(N), since we count the frequency of characters.

Space complexity - O(26), since we store the frequency of characters in the array.

We learned to check whether there is any permutation of two strings such that all characters of one string can be larger than the other string. The first method uses a sorting method, and the second method uses the cumulative frequency of characters.

The above is the detailed content of Checks whether any permutation of a given string is lexicographically greater than another given string. For more information, please follow other related articles on the PHP Chinese website!