Verifique si alguna permutación de una string dada es lexicográficamente más grande que la otra string dada

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:

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)

Publicación traducida automáticamente

Artículo escrito por Kdheeraj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *