Are two strings anagrams?

Question

My code passes all the given test cases. I would like to know a better way to to write the code. Such as a more efficient algorithm for checking if two strings are anagrams.

import java.io.* ;
import java.util.* ;

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    
    String  str1 = input.nextLine().toLowerCase();
    String str2 = input.nextLine().toLowerCase();
    
    char[] temp = str1.toCharArray(); Arrays.sort(temp);
    str1 = new String(temp);
    
    temp = str2.toCharArray(); Arrays.sort(temp);
    str2 = new String(temp);
            
    if(str1.equals(str2) == true) System.out.println("Anagrams");
    else System.out.println("Not Anagrams");
}

Answer 1

Provide Context

Explain what it does in a meaningful method name and JavaDoc comment (in your question as well)

Example:

/**
 * Test if both words are anagrams to each other.
 * <p>Works for lowercase ASCII only.
 * 
 * word           non-blank lowercase word (may have spaces inside)
 * otherWord      ...
 * return         true if word is anagram of otherWord, false else 
 */
public static boolean areAnagrams(String word, String otherWord) {
   // check if anagrams
   return true;
   // if not
   return false;
}

What the method signature reveals to the code reader already:

• public so he can use it
• static behaviour does not depend on class state (each execution is determined by parameters only)
• boolean return signals a kind of test-function, that can be used in if-statments, etc.
• areAnagrams tells what it does (Java-naming convention for boolean tests is prefixing with is, are, has, etc.)

The JavaDoc explains limitations and should also list expected parameters and what is returned when, or what Exception is thrown when errors occur.

Naming

• method: should tell the caller immediately what it does (main is not a catch-all container)
• variable: str1, str2 tell nothing about their purpose (like inputLine or potentialAnagram. temp is even worse (what's in it, where comes from). input is misleading, because it's a scanner to look and extract input from later.

Separation of Concerns

• UI and business-logic should always be separated: text input/output is one concern (class or method) to find similarly in many applications; logic (find anagrams, test and calculate result) are another concern to focus on with domain knowledge;

Why separate (benefits)?

Both can be developed/maintained/adapted/exchanged separately and by different persons simultaneously. They are glued together and aimed to fit like a puzzle by "contract" or design. Here for example: (a) the input provided to logic should always be 2 strings (arbitrary length, non-blank, etc.); whereas the output to the user should be a descriptive message in 2 variants for is-anagram or is-not..; (b) the logic accepts two strings and returns a boolean; (c) the UI-layer should validate input and reject invalid like two empty string; (d) the UI-layer should also convert response from logic like boolean to an output message (it may use the input like "Given line 1 'Ana' and 2 'Gram' are NO anagrams")

---

These 3 categories are just to ease code reading and understanding. Still they may lead to better problem thinking, improve design and optimize implementation.

Answer 2

Sure.

• Create a table of all possible characters (as we talk unicode today, this should not really be a table but rather a hash map or the like.)
• Pass over string 1, recording the character count in the table (i.e. increment the count for each character you encounter.)
• Pass over string 2, decreasing the character count in the table for each character you encounter
• If all counts are zero, you have an anagram.

If we assume input length is \$n\$ and the table size is \$m\$ you'll have two passes of \$m\$ for table initialization and evaluation plus two passes of \$n\$ for the string, which comes down to \$O(n+m)\$.

Answer 3

One line - one statement

This will make the code more readable.

temp = str2.toCharArray();
Arrays.sort(temp);
str2 = new String(temp);
        
if(str1.equals(str2) == true) 
    System.out.println("Anagrams");
else 
    System.out.println("Not Anagrams");

Separate logic and input/output

This look much cleaner:

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);

    String  str1 = input.nextLine().toLowerCase();
    String str2 = input.nextLine().toLowerCase();

    if(isAnagram(str1, str2))
        System.out.println("Anagrams");
    else 
        System.out.println("Not Anagrams");
}
bool isAnagram(String s1, String s2) {...}

All the logic is in isAnagram function; it doesn't mix with input/output and can potentionally be reused in other projects.

Be careful with Unicode

If you are using non-ASCII characters, the effects of toLowerCase/toUpperCase and breaking into characters can be unexpected, like "ß".toUpperCase() producing "SS" or "á" being two characters. I'll assume you're using ASCII character set.

Use Arrays.equals

Arrays.equals method can compare arrays, so you can avoid gathering arrays back in strings.

Algorithm

To compare to strings for being anagrams, you need to find every symbol of one string in another (naive algorithm will give \$O(n^2)\$), and sorting makes it faster (\$O(n log(n))\$). Could it be even faster? Maybe - if you choose the proper sorting algorithm. If you're using ASCII characters only and words are long enough (tens of characters), counting sort will allow you to exchange some memory for speed. You don't even need to recreate a sorted sequence - just:

1. compare lengths
2. add the number of characters in the first string
3. subtract the number of characters in the second string, if you ever get a negative value - the strings are not anagrams.

Answer 4

Consider whitespace and symbols. Do you want "parliament" and "partial men" to match? How about "Internet Anagram Server" and "I, Rearrangement Servant"?

Answer 5

You fell into an often-overlooked trap, which makes your program useless to most of the world. It assumes that one char is one "character" (as users would understand it). Here's where that goes wrong:

🇧🇬
🇬🇧
Anagrams

The first input is the flag of Bulgaria, and the second is the flag of Great Britain. You see, there isn't actually a dedicated Unicode code point for every flag. Instead, there are 26 regional indicator symbols, one for each of the 26 English letters. These are combined into ISO 3166-2 2-letter country codes. In this case, "[B][G]" and "[G][B]". It's then the system's responsibility to identify these country codes, and present a single glyph which shows the latest flag for that country code.

Your program considers these to be anagrams. It would fail in similar spectacular ways for skin-tone-modified emojis, family emojis, many non-latin alphabets (including popular ones like Chinese).

The solution is to operate on the level of "Unicode Extended Grapheme Clusters" rather than chars (which model Unicode scalars). This is the closest thing to a human's understanding of "characters", accounting for things like emoji families, flags, characters with accent modifiers applied to them, and so on. It's not a perfect match, but it's pretty close.

This code snippet from this answer looks like a pretty promising way to decompose a string into its constituent EGCs:

String[] extendedGraphemeClusters = inputString.codePoints()
    .mapToObj(cp -> new String(Character.toChars(cp)))
    .toArray(size -> new String[size]);

You could then use this extendedGraphemeClusters array of strings (where each string is really just an EGC) as the input to the various algorithms discussed in the other answers. E.g. you can use that array with the sorting approach you used originally. Rather than sorting the characters with the input string, you would sort the strings (modeling EGCs) in the array (which models the EGCs of the input string).

You could also use the HashMap based approach with it, just the same.

Answer 6

Add a check of length comparison before sorting. When length of both strings are not same then it should just return false. This will save you on sorting of string performance especially for large input strings.

Answer 7

Sorting takes O(N*log(N)), so of course there is an efficient way to check for Anagrams. Here is an efficient O(N) Time & Space approach to check Anagrams.
Steps involved in checking for ANAGRAMS:

1. If the length of both strings is unequal, then they can never be Anagrams.
2. Convert the strings to Lowercase characters to save memory (as then we only need to deal with 26 characters).
3. Count the frequency of all the alphabets between 'a' to 'z' for both the strings for comparison.
4. Compare the frequency of all the alphabets from 'a' to 'z' of both strings as for being Anagrams to each other, the frequency of each character for both the strings should be equal.
5. If the frequency of any character is found to be unequal, break the loop as it can't be an Anagram. Else they are anagrams.

    static boolean isAnagram(String s1, String s2)
    {
        int n1 = s1.length(), n2 = s2.length();
        if (n1 != n2)
            return false;
        
        int freq[] = new int[26];
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        
        for (int i=0; i<n1; i++)    ++freq[ c1[i]-'a' ];
        for (int i=0; i<n2; i++)    --freq[ c2[i]-'a' ];
        
        for (int i=0; i<26; i++)
            if ( freq[i] != 0 )
                return false;
        return true;
    }

If the string contains characters other than alphabets we need to use a freq array of size 128 or 256 (for extended ASCII characters).

Answer 8

My Code, After few changes made according to fellow user's valuable comments...

Previously my code was able to check only words, now it can able to check (Whitespace, Words only, Sentence with Punctuation). I added the trim() method to both the anagrams strings in the code.

static boolean isAnagram(String x, String y) {
    char[] temp = x.toLowerCase().toCharArray();
    Arrays.sort(temp);
    x = new String(temp);
    
    temp = y.toLowerCase().toCharArray();
    Arrays.sort(temp);
    y = new String(temp);
    
    return x.trim().equals(y.trim());
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    
    if(isAnagram(in.nextLine(), in.nextLine()))
        System.out.println("Anagrams");
    else 
        System.out.println("Not Anagrams");
}

I can't use Arrays.equals() method as I can't trim character array, also I can't use equalsIgnoreCase() just to avoid toLowerCase() as it fails in case like Parliament and partial men.

If the above words are given to program input, the line goes like this if("Paaeilmnrt".trim().equalsIgnoreCase(" aaeilmnprt".trim()) which results in false.