How to check if two String are Anagram of each other - Coding Problem

Hello guys, if you are preparing for Coding interviews then you already know that String is one of the most popular topics. You will bound to get some string-based coding problems on interviews. If not, you have come to the right place becuase we'll look one of the most popular String programming interview questions today,  how to check if two given string 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" is an anagram of each other because they contain 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 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 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 good data structure and algorithm courses like Data Structures and Algorithms: Deep Dive Using Java on Udemy to brush your fundamentals.



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.

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 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?

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Introduction to Algorithms by Thomas H. Corman


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 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.

No comments:

Post a Comment