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>
Producción:
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>
Producción:
true
Complejidad temporal: O(n)
Espacio auxiliar: O(1)