Create anagram buckets from a given input array of words

Carvia Tech | May 18, 2019 | 2 min read | 21 views | Java Coding Challenges


Anagram

Two strings are called anagrams if they contain same set of characters but in different order. For example,

  • peek and keep are anagrams

  • spar and rasp are anagrams

  • listen and silent are anagrams

Here we get an input array of words that contains anagram string, and we need to create buckets for all the anagrams words.

Input:

{"akka", "akak", "baab", "baba", "bbaa"}

Output:

{
    [akka, akak],
    [baab, baba, bbaa]
}

Approach

  1. Create a hashmap that will hold sorted word as the key and list of anagrams as the value. We will use this hashmap to store the results.

  2. For each word in the input array, create a key by sorting the characters and put this word to that list whose key is the sorted word. for example [aakk → akka, akak] If it does not exist then create a new list with the sorted word as key in map.

  3. In the end, traverse the values of hashmap and we get the desired result.

Java Implementation

Anagrams.java
import java.util.*;

public class Anagrams {

    public static void main(String[] args) {
        String[] input = {"akka", "akak", "baab", "baba", "bbaa"};
        Map<String, List<String>> anagramsMap = anagramBuckets(input);
        System.out.println("anagramsMap = " + anagramsMap);
    }

    private static Map<String, List<String>> anagramBuckets(String[] input) {
        Map<String, List<String>> anagramsMap = new HashMap<>(100);
        for (String s : input) {
            char[] word = s.toCharArray();
            Arrays.sort(word);
            String key = String.valueOf(word);
            if (!anagramsMap.containsKey(key)) {
                anagramsMap.put(key, new ArrayList<>());
            }
            anagramsMap.get(key).add(s);
        }
        return anagramsMap;
    }
}

Time Complexity

If we ignore the time consumed by sorting an individual string then we can say that the above approach takes Big O(n) time complexity.

Otherwise the actual time complexity would be O (n log n) (for sorting) + O (n) (for compare)


Java Coding Challenges:
  1. Find two numbers of which the product is maximum in an array
  2. How will you check if a given sentence is a pangram
  3. Java program to check if two strings are anagrams
  4. How to check if the given number is palindrome in Java
  5. Check if the given number is Armstrong Number in Java
  6. Write a program to reverse a string using recursion in Java
  7. Check a number is Prime: Java Coding Problem
See all articles in Java Coding Challenges
Top articles in this category:
  1. Top 50 SDET Java Programming Interview Questions & Answers
  2. Write a program to reverse the order of words in a string
  3. Java program to check if two strings are anagrams
  4. Find longest non-repeating substring from a given string in Java
  5. How to check if the given number is palindrome in Java
  6. Find two numbers of which the product is maximum in an array
  7. Creating custom exceptions in Java



Find more on this topic:
SDET Interviews image
SDET Interviews

End to end automation testing using Selenium Web Driver, Rest Assured, JMeter, Junit, TestNG etc.

Last updated 1 month ago


Recommended books for interview preparation:

This website uses cookies to ensure you get the best experience on our website. more info