Compruebe si algún anagrama de la string S es lexicográficamente más pequeño que el de la string T

Dadas dos strings S y T , la tarea es verificar si algún anagrama de la string S es lexicográficamente más pequeño que cualquier anagrama de la string T.

Ejemplo:

Entrada: S = “xy”, T = “axy”
Salida:
Explicación: Reorganice yx en xy y axy en yxa. Entonces, xy<yxa.

Entrada: S = “cd”, T = “abc”
Salida: No

 

Enfoque: El enfoque consiste en verificar si el anagrama lexicográficamente más pequeño de la string S es más pequeño que el anagrama lexicográficamente más grande de la string T. Si es así, entonces la respuesta es . De lo contrario, no . Ahora, siga los pasos a continuación para resolver esta pregunta:

  1. Ordene la string S para obtener su anagrama lexicográficamente más pequeño.
  2. Ordene a la inversa la string T para obtener su anagrama lexicográficamente más grande.
  3. Compruebe si la nueva string T es mayor que la nueva string S o no. Si es así, imprima . 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 any anagram
// of string S is lexicographically
// smaller than any anagram of string T
void CompareAnagrams(string S, string T)
{
    // Sort string S
    sort(S.begin(), S.end());
 
    // Reverse sort string T
    sort(T.begin(), T.end(), greater<char>());
 
 
    // Comparing both the strings
    if (S.compare(T) < 0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}
 
// Driver code
int main()
{
    string S = "cd";
    string T = "abc";
 
    CompareAnagrams(S, T);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG
{
   
    // function to Reverse String
    static String ReverseString(String myStr)
    {
        String nstr = "";
        char ch;
 
        for (int i = 0; i < myStr.length(); i++) {
            ch = myStr.charAt(i); // extracts each character
            nstr
                = ch + nstr; // adds each character in
                             // front of the existing string
        }
 
        return nstr;
    }
   
    // function to print string in sorted order
    static String sortString(String str)
    {
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        return new String(arr);
    }
 
    // Function to check if any anagram
    // of string S is lexicographically
    // smaller than any anagram of string T
    static void CompareAnagrams(String S, String T)
    {
 
        // Sort string S
        sortString(S);
 
        // Reverse sort string T
        T = sortString(T);
        T = ReverseString(T);
 
        // Comparing both the strings
        if (S.compareTo(T) < 0) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String S = "cd";
        String T = "abc";
 
        CompareAnagrams(S, T);
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python 3 program for the above approach
 
# Function to check if any anagram
# of string S is lexicographically
# smaller than any anagram of string T
 
 
def CompareAnagrams(S,  T):
 
    # Sort string S
    S = list(S)
    S.sort()
    S = ''.join(S)
 
    # Reverse sort string T
    T = list(T)
    T.sort(reverse=True)
    T = ''.join(T)
 
    # Comparing both the strings
    if (S < T):
        print("Yes")
 
    else:
        print("No")
 
# Driver code
if __name__ == "__main__":
 
    S = "cd"
    T = "abc"
 
    CompareAnagrams(S, T)
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
 
public class GFG
{
   
// function to Reverse String
static string ReverseString(string myStr)
    {
        char[] myArr = myStr.ToCharArray();
        Array.Reverse(myArr);
        return new string(myArr);
    }
 
// function to print string in sorted order
    static void sortString(String str) {
        char []arr = str.ToCharArray();
        Array.Sort(arr);
        String.Join("",arr);
    }
 
// Function to check if any anagram
// of string S is lexicographically
// smaller than any anagram of string T
static void CompareAnagrams(string S, string T)
{
   
    // Sort string S
    sortString(S);
 
    // Reverse sort string T
    sortString(T);
    ReverseString(T);
     
 
    // Comparing both the strings
    if (string.Compare(S, T) < 0) {
        Console.WriteLine("Yes");
    }
    else {
        Console.WriteLine("No");
    }
}
 
// Driver Code
public static void Main(String []args) {
     
    string S = "cd";
    string T = "abc";
 
    CompareAnagrams(S, T);
}
}
 
// This code is contributed by target_2.

Javascript

<script>
 
    // JavaScript Program to implement
    // the above approach
 
    // function to Reverse String
    function ReverseString(myStr)
    {
        let nstr = "";
        let ch;
 
        for (let i = 0; i < myStr.length; i++) {
            ch = myStr[i]; // extracts each character
            nstr
                = ch + nstr; // adds each character in
                             // front of the existing string
        }
 
        return nstr;
    }
   
    // function to print string in sorted order
    function sortString(str)
    {
        let arr = str.split();
        arr.sort();
        return arr.join();
    }
 
    // Function to check if any anagram
    // of string S is lexicographically
    // smaller than any anagram of string T
    function CompareAnagrams(S, T)
    {
 
        // Sort string S
        sortString(S);
 
        // Reverse sort string T
        T = sortString(T);
        T = ReverseString(T);
 
        // Comparing both the strings
        if (S.localeCompare(T) < 0) {
            document.write("Yes");
        }
        else {
            document.write("No");
        }
    }
 
    // Driver code
 
    let S = "cd";
    let T = "abc";
 
    CompareAnagrams(S, T);
 
// This code is contributed by sanjoy_62.
</script>
Producción

No

Complejidad de tiempo: O(N*logN)  
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por 18bhupenderyadav18 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 *