Saturday, January 28, 2023

[Solved] How to check if two String are Anagram in Java? Example

Hello guys, if you are preparing for Coding interviews then you already know that String is one of the most popular topics. You will be bound to get some string-based coding problems on interviews. If not, you have come to the right place becuase we'll look at one of the most popular String programming interview questions today,  how to check if two given strings are Anagram of each other? Two String is said to be an anagram of each other, if they contain exactly the same characters but in a different order. For example "ARMY" and "MARY" are an anagram of each other because they contain the exact same characters 'A', 'R', 'M' and  'Y'.

The order doesn't matter, as long as both Strings contains exactly the same character and the same number of time they are Anagram. For example, if one letter is repeated on one String and not on the other then they will not be Anagram of each other.

Another example of Anagram is "Tokyo" and "Kyoto", two of the most popular cities in Japan. Interestingly both have also served as the capital of Japan, Kyoto was the old capital before they moved the capital to Tokyo in the 16th century.

For the sake of simplicity, you can also assume that your solution need not be case-sensitive, which means both army and mary can be matched as an anagram of each other.

Btw, strong knowledge of data structure and algorithm is expected in coding interviews. At the bare minimum, you should be familiar with essential data structures like an array, string, linked list, binary tree, binary search tree, balanced tree, stack, queue, heap, and graphs. 

If you want to learn more about fundamental data structures, I suggest you join a comprehensive data structure and algorithm course on Udemy to brush your fundamentals. If you need recommendations check this list of best data structure and algorithms courses on Medium. 




Java Program to find if two String are Anagram or not

Here is a Java program to check if two String is an anagram of each other or not. This program uses the same logic described to find if given strings are anagram or not. The program has two methods of checking for Anagram. 

The first method uses a couple of library methods while the second method doesn't use any library method. If you are preparing for coding interviews then practicing this kind of problem is really important as you will learn how to solve a given problem using library methods and without using them. 

I also recommend you check out Grokking the Coding Interview: Patterns for Coding Questions course on Educative. It's a text-based course where you can practice coding patterns in the browser. The good thing about this is that you will learn 16 useful coding patterns like Sliding Window, Two Pointers, Fast and Slow Pointers, Merge Intervals, Cyclic Sort, and Top K elements that can help you to solve zones of frequently asked coding problems. 

string anagram coding problem


Now, let's the Java program to check if given Strings are anagrams or not. You can also run this program in your IDE or from the command line by creating a Java file. This problem has also been asked in many big companies like Facebook, Microsoft, and Amazon coding interviews

import java.util.Arrays;

/**
* Java Program to check if two String is an anagram of each other or not. Two
* String is said to be an anagram of each other, if they contain exactly same
* characters but in a different order. For example "army" and "mary" are anagram
* of each other because they contain exact same characters 'a', 'r', 'm' and
* 'y'.
*
* @author javinpaul
*/

public class Testing {



    public static void main(String args[]) {



        String[][] data = {{"army", "mary"}, {"stop", "tops"}, {"soap", "abcd"}};

        System.out.println("======== Testing areAnagrams() method =======");

        for (String[] value : data) {

            String s1 = value[0];

            String s2 = value[1];

            System.out.printf("Are %s and %s are Anagrams? %b%n", s1, s2,
                       areAnagrams(s1, s2));

        }



        System.out.println("======== Testing isAnagaram() method =======");

        for (String[] value : data) {

            String s1 = value[0];

            String s2 = value[1];

            System.out.printf("Does %s and %s are Anagrams? %b%n", s1, s2, 
                               isAnagram(s1, s2));

        }



    }



    /*

     * One of the easiest way to check if two Strings are an anagram of each other
     * is to take their character array, sort them and check if they are equal.
     * If sorted character arrays are equal then both String are an anagram of
     * each other.

     */

    public static boolean areAnagrams(String first, String second) {

        char[] fa = first.toCharArray();
        char[] sa = second.toCharArray();

        // sort arrays
        Arrays.sort(fa);
        Arrays.sort(sa);


        // check if arrays are equal
        if (Arrays.equals(fa, sa)) {
            return true;
        }


        return false;

    }



    /*

     * Earlier method was using a couple of library methods, which is not permitted during
     * interviews. This method checks if two Strings are anagram without using any utility
     * method. This solution assumes that both source and target string are ASCII strings.

     */

    public static boolean isAnagram(String source, String target) {

        if ((source == null || target == null) || source.length() != target.length()) {

            return false;

        }



        int[] table = new int[256];



        int numOfUniqueCharInSource = 0;

        int numOfCharProcessedInTarget = 0;



        char[] characters = source.toCharArray();



        // store count of each unique character in source String

        for (char ch : characters) {

            if (table[ch] == 0) {

                ++numOfUniqueCharInSource;

            }

            ++table[ch];

        }



        for (int i = 0; i < target.length(); ++i) {

            int c = target.charAt(i);

            if (table[c] == 0) {

                return false;

            }

            --table[c];

            if (table[c] == 0) {

                ++numOfCharProcessedInTarget;

                if (numOfCharProcessedInTarget == numOfUniqueCharInSource) {

                   // its a match if t has been processed completely

                    return i == target.length() - 1;

                }

            }

        }

        return false;



    }



}



Output

======== Testing areAnagrams() method =======

Are army and mary are Anagrams? true

Are stop and tops are Anagrams? true

Are soap and abcd are Anagrams? false

======== Testing isAnagaram() method =======

Does army and mary are Anagrams? true

Does stop and tops are Anagrams? true

Does soap and abcd are Anagrams? false


That's all about how to check if two String is Anagram of each other or not. If you need more String based coding problems for practice then you can also solve the problems listed below.  It's an interesting problem and there are a couple of invariants as well as the case-sensitive one I discussed in the first paragraph. You may also be asked to calculate the time and space complexity of this problem, can you calculate it?


More String Problems to solve
If you are interested in solving more String based algorithm problems then here is the list of some of the frequently asked questions.
  • How to Print duplicate characters from String? (solution)
  • How to check if two Strings are anagrams of each other? (solution)
  • How to program to print the first non-repeated character from String? (solution)
  • How to reverse String in Java using Iteration and Recursion? (solution)
  • How to check if a string contains only digits?  (solution)
  • How to find duplicate characters in a String? (solution)
  • How to count the number of vowels and consonants in a String? (solution)
  • How to count the occurrence of a given character in String? (solution)
  • How to convert a numeric string to an int? (solution)
  • How to find all permutations of String? (solution)
  • 10 Algorithms Courses to Crack Programming Job Interviews (courses)
  • How to reverse words in a sentence without using a library method? (solution)
  • How to check if String is Palindrome? (solution)
  • How to return the highest occurred character in a String? (solution)
  • How to reverse a String in place in Java? (solution)
  • 50+ Data Structure and Algorithms Interview Questions (questions)

Thanks for reading this coding interview question so far. If you like this String interview question then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.

P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.

2 comments:

  1. O(n) algorithm is straightforward, where n is length of the string. Keep count for number of times each character appears in string. If more than one character appears odd number of times, the string cannot be anagram of a palindrome, otherwise string is anagram of a palindrome.

    ReplyDelete
  2. Anagrams are fun! Just like the word "listen" turning into "silent" or how "astronomer" can be whimsically rearranged into "moon starer."

    While the method using sorting seems to operate at a time complexity of O(n log n) due to the sorting process, the second method appears more efficient, with a rough estimate of O(n), as it traverses through each string only once

    ReplyDelete

Feel free to comment, ask questions if you have any doubt.