Given two strings S and T, the task is to check if any anagram of string S is lexicographically smaller than any anagram of string T.
Example:
Input: S = “xy”, T = “axy”
Output: Yes
Explanation: Rearrange yx into xy and axy into yxa. Then, xy<yxa.Input: S = “cd”, T = “abc”
Output: No
Approach: The approach is to check if the lexicographically smallest anagram of the string S is smaller than the lexicographically largest anagram of string T. If it is, then the answer is Yes. Otherwise, No. Now, follow the below steps to solve this question:
- Sort string S to get its lexicographically smallest anagram.
- Reverse sort string T to get its lexicographically largest anagram.
- Check if the new string T is greater than the new string S or not. If it is, print Yes. Otherwise, print No.
Below is the implementation of the above approach.
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 Tvoid 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 codeint main(){ string S = "cd"; string T = "abc"; CompareAnagrams(S, T); return 0;} |
Java
// Java program for the above approachimport 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 Tdef 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 codeif __name__ == "__main__": S = "cd" T = "abc" CompareAnagrams(S, T) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;public class GFG{ // function to Reverse Stringstatic 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 Tstatic 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 Codepublic 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> |
Output
No
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments