Dadas dos strings str1 y str2 de la misma longitud N , la tarea es verificar si existe alguna permutación posible en cualquiera de las strings dadas, de modo que cada carácter de una string sea mayor o igual a cada carácter de la otra string, en el correspondiente índices. Devuelve verdadero si existe permutación; de lo contrario, es falso.
Ejemplo:
Entrada: str1 = «adb», str2 = «cda»
Salida: verdadero
Explicación: después de la permutación str1 = «abd» y str2 = «acd», por lo que cada carácter de str2 es mayor o igual a cada carácter de s1.Entrada: str1 = «gfg», str2 = «agd»
Salida: verdadero
Enfoque: el problema anterior se puede resolver clasificando ambas strings y luego comparándolas lexicográficamente.
Siga los pasos a continuación para entender cómo:
- Convertir strings dadas en una array de caracteres
- Ordenar ambas arrays de caracteres
- Ahora, itere a través de estas arrays y verifique si cada carácter de una array es mayor o igual que el carácter correspondiente en otra array
- Si se encuentra lexicográficamente más grande, escriba verdadero, de lo contrario, falso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach #include <algorithm> #include <iostream> #include <string> using namespace std; bool checkGreaterOrNot(string str1, string str2) { // Sorting both strings sort(str1.begin(), str1.end()); sort(str2.begin(), str2.end()); // Checking if any string //is greater or not bool flag = true; for (int i = 0; i < str1.length(); i++) { if (str1[i] < str2[i]) { flag = false; break; } } // If str1 is greater returning true if (flag) return true; flag = true; for(int i = 0; i < str2.length(); i++){ if (str1[i] > str2[i]) { return false; } } // If str2 is greater returning true return true; } int main() { string str1 = "adb"; string str2 = "cda"; bool ans = checkGreaterOrNot(str1, str2); if (ans) { cout << "true"; } else { cout << "false"; } return 0; } // This code is contributed by Kdheeraj.
Java
// Java implementation for the above approach import java.io.*; import java.util.*; class GFG { public static boolean checkGreaterOrNot(String str1, String str2) { // Sorting strings char[] arr1 = str1.toCharArray(); Arrays.sort(arr1); char[] arr2 = str2.toCharArray(); Arrays.sort(arr2); boolean flag = true; // str1 is greater // if it does not break the loop for (int i = 0; i < arr1.length; i++) { if (arr1[i] < arr2[i]) { flag = false; break; } } // If str1 is greater returning true if (flag) return true; flag = true; // If characters of str1 is greater // then none of the strings have all // corresponding characters greater // so return false for (int i = 0; i < arr2.length; i++) { if (arr1[i] > arr2[i]) { return false; } } // If str2 is greater returning true return true; } // Driver code public static void main(String[] args) { String str1 = "adb"; String str2 = "cda"; boolean ans = checkGreaterOrNot(str1, str2); System.out.println(ans); } }
Python3
# Python 3 implementation for the above approach def checkGreaterOrNot(str1, str2): # Sorting both strings str1 = sorted(str1) str1 = "".join(str1) str2 = sorted(str2) str2 = "".join(str2) # Checking if any string #is greater or not flag = True for i in range(len(str1)): if(str1[i] < str2[i]): flag = False break # If str1 is greater returning true if (flag): return True flag = True for i in range(len(str2)): if (str1[i] > str2[i]): return False # If str2 is greater returning true return True # Driver code if __name__ == '__main__': str1 = "adb" str2 = "cda" ans = checkGreaterOrNot(str1, str2) if (ans): print("true") else: print("false") # This code is contributed by ipg2016107.
C#
// C# implementation for the above approach using System; class GFG { public static bool checkGreaterOrNot(string str1, string str2) { // Sorting strings char[] arr1 = str1.ToCharArray(); Array.Sort(arr1); char[] arr2 = str2.ToCharArray(); Array.Sort(arr2); bool flag = true; // str1 is greater // if it does not break the loop for (int i = 0; i < arr1.Length; i++) { if (arr1[i] < arr2[i]) { flag = false; break; } } // If str1 is greater returning true if (flag) return true; flag = true; // If characters of str1 is greater // then none of the strings have all // corresponding characters greater // so return false for (int i = 0; i < arr2.Length; i++) { if (arr1[i] > arr2[i]) { return false; } } // If str2 is greater returning true return true; } // Driver code public static void Main(string[] args) { string str1 = "adb"; string str2 = "cda"; bool ans = checkGreaterOrNot(str1, str2); Console.WriteLine(ans); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript Program to implement // the above approach function checkGreaterOrNot(str1, str2) { // Sorting both strings str1.sort(function (a, b) { return a.charCodeAt(0) - b.charCodeAt(0); }); str2.sort(function (a, b) { return a.charCodeAt(0) - b.charCodeAt(0); }); // Checking if any string //is greater or not let flag = true; for (let i = 0; i < str1.length; i++) { if (str1[i].charCodeAt(0) > str2[i].charCodeAt(0)) { flag = false; break; } } // If str1 is greater returning true if (flag) return true; flag = true; for (let i = 0; i < str2.length; i++) { if (str1[i].charCodeAt(0) > str2[i].charCodeAt(0)) { return false; } } // If str2 is greater returning true return true; } let str1 = ['a', 'd', 'b']; let str2 = ['c', 'd', 'a'] let ans = checkGreaterOrNot(str1, str2); if (ans) { document.write("true"); } else { document.write("false"); } // This code is contributed by Potta Lokesh </script>
true
Complejidad de Tiempo: O(n*log n)
Espacio Auxiliar: O(n)
Enfoque 2: el enfoque anterior se puede optimizar utilizando el mapa de frecuencia para strings dadas.
- Haz un mapa de frecuencia para ambas strings dadas
- Cree variables count1 y count2 para indicar la frecuencia acumulada de las strings respectivas
- Iterar a través del mapa de frecuencia y verificar si el valor de cualquier string es mayor que la otra o no.
- En caso afirmativo, escriba verdadero. De lo contrario, imprima falso.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach #include <iostream> #include <string> using namespace std; bool checkGreaterOrNot(string str1, string str2) { int arr1[26] = { 0 }; int arr2[26] = { 0 }; // Making frequency map for both strings for (int i = 0; i < str1.length(); i++) { arr1[str1[i] - 'a']++; } for (int i = 0; i < str2.length(); i++) { arr1[str2[i] - 'a']++; } // To check if any array // is greater to the other or not bool str1IsSmaller = false, str2IsSmaller = false; int count1 = 0, count2 = 0; for (int i = 0; i < 26; i++) { count1 += arr1[i]; count2 += arr2[i]; if (count1 > count2) { // None of the strings have // all corresponding characters // greater than other string if (str2IsSmaller) return false; str1IsSmaller = true; } if (count1 < count2) { // None of the strings have // all corresponding characters // greater than other string if (str1IsSmaller) return false; str2IsSmaller = true; } } return true; } // Driver code int main() { string str1 = "geeks"; string str2 = "peeks"; bool ans = checkGreaterOrNot(str1, str2); if (ans) { cout << "true"; } else { cout << "false"; } } // This code is contributed by Kdheeraj.
Java
// Java implementation for the above approach import java.util.*; class GFG { public static boolean checkGreaterOrNot( String str1, String str2) { int[] freq1 = new int[26]; int[] freq2 = new int[26]; // Making frequency map // for both strings for (int i = 0; i < str1.length(); i++) { freq1[str1.charAt(i) - 'a']++; } for (int i = 0; i < str2.length(); i++) { freq2[str2.charAt(i) - 'a']++; } boolean str1IsSmaller = false; boolean str2IsSmaller = false; int count1 = 0, count2 = 0; // Checking if any array // is strictly increasing or not for (int i = 0; i < 26; i++) { count1 += freq1[i]; count2 += freq2[i]; if (count1 > count2) { // None of the strings have // all corresponding characters // greater than other string if (str2IsSmaller) return false; str1IsSmaller = true; } else if (count2 > count1) { // None of the strings have // all corresponding characters // greater than other string if (str1IsSmaller) return false; str2IsSmaller = true; } } return true; } // Driver code public static void main(String[] args) { String str1 = "geeks"; String str2 = "peeks"; boolean ans = checkGreaterOrNot(str1, str2); System.out.println(ans); } }
Python3
# python implementation for the above approach def checkGreaterOrNot(str1, str2): arr1 = [0 for x in range(26)] arr2 = [0 for x in range(26)] # Making frequency map for both strings for val in str1: arr1[ord(val)-97] += 1 for val in str2: arr1[ord(val)-97] += 1 # To check if any array # is greater to the other or not str1IsSmaller = False str2IsSmaller = False count1 = 0 count2 = 0 for i in range(0, 26): count1 += arr1[i] count2 += arr2[i] if (count1 > count2): # None of the strings have # all corresponding characters # greater than other string if str2IsSmaller == True: return False str1IsSmaller = True if (count1 < count2): # None of the strings have # all corresponding characters # greater than other string if str1IsSmaller == True: return False str2IsSmaller = True return True # Driver code str1 = "geeks" str2 = "peeks" ans = checkGreaterOrNot(str1, str2) if ans == True: print("true") else: print("false") # This code is contributed by amreshkumar3.
C#
// C# program for the above approach using System; class GFG { public static bool checkGreaterOrNot( string str1, string str2) { int[] freq1 = new int[26]; int[] freq2 = new int[26]; // Making frequency map // for both strings for (int i = 0; i < str1.Length; i++) { freq1[str1[(i)] - 'a']++; } for (int i = 0; i < str2.Length; i++) { freq2[str2[(i)] - 'a']++; } bool str1IsSmaller = false; bool str2IsSmaller = false; int count1 = 0, count2 = 0; // Checking if any array // is strictly increasing or not for (int i = 0; i < 26; i++) { count1 += freq1[i]; count2 += freq2[i]; if (count1 > count2) { // None of the strings have // all corresponding characters // greater than other string if (str2IsSmaller) return false; str1IsSmaller = true; } else if (count2 > count1) { // None of the strings have // all corresponding characters // greater than other string if (str1IsSmaller) return false; str2IsSmaller = true; } } return true; } // Driver Code public static void Main() { string str1 = "geeks"; string str2 = "peeks"; bool ans = checkGreaterOrNot(str1, str2); Console.WriteLine(ans); } } // This code is contributed by avijitmondal1998.
Javascript
<script> // Javascript implementation for the above approach function checkGreaterOrNot(str1, str2) { var arr1 = Array(26).fill(0); var arr2 = Array(26).fill(0); // Making frequency map for both strings for (var i = 0; i < str1.length; i++) { arr1[str1[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } for (var i = 0; i < str2.length; i++) { arr1[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } // To check if any array // is greater to the other or not var str1IsSmaller = false, str2IsSmaller = false; var count1 = 0, count2 = 0; for (var i = 0; i < 26; i++) { count1 += arr1[i]; count2 += arr2[i]; if (count1 > count2) { // None of the strings have // all corresponding characters // greater than other string if (str2IsSmaller) return false; str1IsSmaller = true; } if (count1 < count2) { // None of the strings have // all corresponding characters // greater than other string if (str1IsSmaller) return false; str2IsSmaller = true; } } return true; } // Driver code var str1 = "geeks"; var str2 = "peeks"; var ans = checkGreaterOrNot(str1, str2); if (ans) { document.write("true"); } else { document.write("false"); } // This code is contributed by rutvik_56. </script>
true
Complejidad temporal: O(n)
Espacio auxiliar: O(1)