Check if any anagram of string S is lexicographically smaller than that of string T

Intuition

An anagram is a word or phrase formed by rearranging the letters of another word or phrase. 

For example, "listen" and "silent" are anagrams of each other because they have the same letters but in different order.

Now, let's say we want to check if any anagram of string S is lexicographically smaller than that of string T. 

What is lexicographically small? 

The lexicographically smaller string refers to the string that comes first in alphabetical order when comparing two or more strings character by character.

To determine which string is lexicographically smaller, we begin by comparing the first character of each string. 

• If the first character of the first string is less than the first character of the second string, the first string is lexicographically smaller or vice versa. 
   
• If the first characters are the same, we continue to compare the second characters, and so on, until we find a character that is different.
   

For example, consider the following strings:

"apple"

"banana"

"cheery"

"date"
 

=> In this example, "apple" is lexicographically smaller than "banana" because 'a' comes before 'b' in the alphabet. 

=>"banana" is lexicographically smaller than "cheery" because the first two characters are the same, but 'b' comes before 'c' in the alphabet. 

=>"cheery" is lexicographically smaller than "date" because 'c' comes before 'd' in the alphabet.

Approach - Using Sorting

In this approach, we will be using the sorting algorithm to sort the string S in ascending order and String T in descending order. 

If you think carefully about the problem statement, we need to find the anagram that may come smaller than any anagram of String T. 

By using the Sorting algorithm, we can compare the sorted strings to see if the lexicographically smallest anagram of S is smaller than the lexicographically largest anagram of T.

If it is so, i.e., means there exists an anagram that satisfies the condition. 

Otherwise, we will return false. 

Algorithm

1. Sort the characters of string S in ascending order.
    
2. Sort the characters of string T in descending order.
    
3. Compare the sorted strings to see if the lexicographically smallest anagram of S is smaller than the lexicographically largest anagram of T.
    

Code in C++

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool isLexicographicallySmallerAnagram(string S, string T) {

    // Sort string S in ascending order
    sort(S.begin(), S.end());
    
    // Sort string T in descending order
    sort(T.begin(), T.end(), greater<char>());
    
    // Compare the sorted strings to check if the lexicographically smallest anagram of S is smaller than the lexicographically largest anagram of T
    return S < T;
    
}
int main() {
    string S = "code";
    string T = "ninja";
    
    if (isLexicographicallySmallerAnagram(S, T)) {
        cout << "Yes, there exists an anagram of " << S << " which is lexicographically smaller than any anagram of " << T << endl;
    } else {
        cout << "No, there is no anagram of " << S << " which is lexicographically smaller than any anagram of " << T << endl;
    }
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Yes, there exists an anagram of code which is lexicographically smaller than any anagram of ninja. 

Code in Java

import java.util.*;
class Main {
    static boolean isLexicographicallySmallerAnagram(String S, String T) {
    
        // Sort string S in ascending order
        
        char[] sChars = S.toCharArray();
        Arrays.sort(sChars);
        
        S = new String(sChars);
        
        // Sort string T in descending order
        
        char[] tChars = T.toCharArray();
        Arrays.sort(tChars);
        
        T = new StringBuilder(new String(tChars)).reverse().toString();
        // Compare the sorted strings to check if the lexicographically smallest anagram of S is smaller than the lexicographically largest anagram of T
        
        return S.compareTo(T) < 0;
        
    }
    public static void main(String[] args) {
        String S = "code";
        String T = "ninja";
        
        if (isLexicographicallySmallerAnagram(S, T)) {
            System.out.println("Yes, there exists an anagram of " + S + " which is lexicographically smaller than any anagram of " + T);
        } else {
            System.out.println("No, there is no anagram of " + S + " which is lexicographically smaller than any anagram of " + T);
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Yes, there exists an anagram of code which is lexicographically smaller than any anagram of ninja. 

You can also try this code with Online Java Compiler

Run Code

Explanation

Time Complexity

O(n log n), where n is the length of the input string. The function calls sort twice, so the overall time complexity is O(2n log n) which simplifies to O(n log n).

Space Complexity

O(1), since we are not using any extra space.

Frequently Asked Questions

What is an anagram? Give an example of an anagram. 

An anagram is a word or phrase formed by rearranging the letters of another word or phrase. In other words, two words are said to be anagrams of each other if they use the same letters in a different order to form a new word. 

For example, abba  is an anagram of baba. 

Which sorting algorithm is the fastest?

In practice, Quick Sort is usually the fastest sorting algorithm. Its performance is measured most of the time in O(N × log N).

What is the stability of sorting algorithms?

A stable sorting algorithm maintains the relative order of the items with equal sort keys.

Conclusion 

This article discussed the problem of checking if any anagram of string S is lexicographically smaller than that of string T. We have discussed one approach to solve this problem. 

We have also discussed the time and space complexity of the approach.

Recommended Reading

• STL in C++
• String Algorithms
• Basic String Problems
• Reverse A String In C
• Palindrome number in python

Recommended Problems

• String Palindrome
• Check Palindrome
• Number Theory Problems
• Longest Palindromic Subsequence
• Aggressive Cows
   

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio. 

Happy Coding!