Dadas dos strings str1 y str2 , la tarea es verificar si es posible alguna permutación de las strings dadas str1 y str2 de modo que el carácter en cada índice de una string sea mayor o igual que la otra string.
Ejemplos:
Entrada: A = «abc», B = «xya»
Salida: Sí
Explicación:
«ayx» es una permutación de B = «xya» que puede dividirse en la string «abc», que es una permutación de A = «abc».Entrada: A = “abe”, B = “acd”
Salida: “No”
Enfoque ingenuo: la idea es generar toda la permutación de una string y verificar si cada carácter de cualquier permutación es mayor que la otra string, luego imprimir «SÍ», de lo contrario, imprimir «NO».
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)
Enfoque eficiente: ya que tenemos que verificar si cada carácter de permutación de una string es mayor o igual a la permutación de otra string o no. La idea es ordenar ambas strings en orden alfabético . Ahora itere un bucle sobre todo el carácter de la string si toda la string de string str1 es menor que str2 o todo el carácter de la string str2 es menor que str1, luego imprima Sí , de lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if permutation of
// one string can break permutation of
// another string or not
bool CanBreak(string A, string B)
{
// Sort both the strings
// in alphabetical order
sort(A.begin(), A.end());
sort(B.begin(), B.end());
bool ans1 = true, ans2 = true;
// Iterate over the strings
for (int i = 0; i < A.length(); i++) {
// If any of the string can break
// other then mark ans as false;
if (A[i] < B[i])
ans1 = false;
if (B[i] < A[i])
ans2 = false;
}
// If any of the string can break
return ans1 || ans2;
}
// Driver Code
int main()
{
// Given string A and B
string A = "abc", B = "xya";
// Function Call
if (CanBreak(A, B))
cout << "Yes";
else
cout << "No";
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if permutation of
// one String can break permutation of
// another String or not
static boolean CanBreak(String A, String B)
{
// Sort both the Strings
// in alphabetical order
A = sortString(A);
B = sortString(B);
boolean ans1 = true, ans2 = true;
// Iterate over the Strings
for(int i = 0; i < A.length(); i++)
{
// If any of the String can break
// other then mark ans as false;
if (A.charAt(i) < B.charAt(i))
ans1 = false;
if (B.charAt(i) < A.charAt(i))
ans2 = false;
}
// If any of the String can break
return ans1 || ans2;
}
static String sortString(String inputString)
{
// Convert input string to char array
char tempArray[] = inputString.toCharArray();
// Sort tempArray
Arrays.sort(tempArray);
// Return new sorted string
return new String(tempArray);
}
// Driver Code
public static void main(String[] args)
{
// Given String A and B
String A = "abc", B = "xya";
// Function call
if (CanBreak(A, B))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for
# the above approach
# Function to check if
# permutation of one string
# can break permutation of
# another string or not
def CanBreak(A, B):
# Sort both the strings
# in alphabetical order
A = "".join(sorted(A))
B = "".join(sorted(B))
ans1 = True
ans2 = True
# Iterate over the strings
for i in range(len(A)):
# If any of the string
# can break other then
# mark ans as false;
if(A[i] < B[i]):
ans1 = False
if(B[i] < A[i]):
ans2 = False
# If any of the string
# can break
return (ans1 or ans2)
# Driver Code
# Given string A and B
A = "abc"
B = "xya"
# Function Call
if(CanBreak(A, B)):
print("Yes")
else:
print("No")
# This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if permutation of
// one String can break permutation of
// another String or not
static bool CanBreak(String A, String B)
{
// Sort both the Strings
// in alphabetical order
A = sortString(A);
B = sortString(B);
bool ans1 = true, ans2 = true;
// Iterate over the Strings
for(int i = 0; i < A.Length; i++)
{
// If any of the String can break
// other then mark ans as false;
if (A[i] < B[i])
ans1 = false;
if (B[i] < A[i])
ans2 = false;
}
// If any of the String can break
return ans1 || ans2;
}
static String sortString(String inputString)
{
// Convert input string to char array
char []tempArray = inputString.ToCharArray();
// Sort tempArray
Array.Sort(tempArray);
// Return new sorted string
return new String(tempArray);
}
// Driver Code
public static void Main(String[] args)
{
// Given String A and B
String A = "abc", B = "xya";
// Function call
if (CanBreak(A, B))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program for the above approach
// Function to check if permutation of
// one String can break permutation of
// another String or not
function CanBreak(A, B)
{
// Sort both the Strings
// in alphabetical order
A = sortString(A);
B = sortString(B);
let ans1 = true, ans2 = true;
// Iterate over the Strings
for(let i = 0; i < A.length; i++)
{
// If any of the String can break
// other then mark ans as false;
if (A[i] < B[i])
ans1 = false;
if (B[i] < A[i])
ans2 = false;
}
// If any of the String can break
return ans1 || ans2;
}
function sortString(inputString)
{
// Convert input string to char array
let tempArray = inputString.split('');
// Sort tempArray
tempArray.sort();
// Return new sorted string
return new String(tempArray);
}
// Driver Code
// Given String A and B
let A = "abc", B = "xya";
// Function call
if (CanBreak(A, B))
document.write("Yes");
else
document.write("No");
</script>
Yes
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)