Mastering Unique Elements and Anagram Detection with Java HashSets

Mastering Unique Elements and Anagram Detection with Java HashSets | CodeSignal Learn

Introduction

Welcome to our focused exploration of Java's HashSet and its remarkable applications in solving algorithmic challenges. In this lesson, " Mastering Unique Elements and Anagram Detection with Java HashSets," we'll explore how this powerful data structure can be used to approach and solve certain types of problems commonly encountered in technical interviews.

Problem 1: Unique Echo

Picture this: you're given a vast list of words, and you must identify the final word that stands proudly solitary — the last word that is not repeated. Imagine sorting through a database of unique identifiers and finding one identifier towards the end of the list that is unlike any others.

Problem 1: Naive Approach

O(n^2)

Problem 1: Efficient Approach

O(n)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Problem 2: Solution Building

O(m\log m)

Let's break down the anagram matcher:

Construct a method to create sorted character signatures from the input string:

Java

private static String sortCharacters(String input) {
   char[] chars = input.toCharArray();
   Arrays.sort(chars);
   return new String(chars);
}

Store these sorted characters from array2 in a HashSet for fast lookup:

Java

HashSet<String> sortedWordsInArray2 = new HashSet<>();
for (String word : array2) {
   sortedWordsInArray2.add(sortCharacters(word));
}

For each word in array1, check for its sorted signature in the HashSet and track the found anagrams:

Java

HashSet<String> anagramsMatched = new HashSet<>();
ArrayList<String> result = new ArrayList<>();
for (String word : array1) {
    if (sortedWordsInArray2.contains(sortCharacters(word))) {
        if (!anagramsMatched.contains(word)) {
            result.add(word);
            anagramsMatched.add(word);
        }
    }
}

HashSet<String> anagramsMatched = new HashSet<>();
ArrayList<String> result = new ArrayList<>();
for (String word : array1) {
    if (sortedWordsInArray2.contains(sortCharacters(word))) {
        if (!anagramsMatched.contains(word)) {
            result.add(word);
            anagramsMatched.add(word);
        }
    }
}

The ArrayList result stores the matches, ensuring that we return unique anagrams, while the HashSet anagramsMatched prevents duplication in our result.

Our final step is to return the list of anagrams found:

Java

return result;

return result;

By utilizing HashSets in this manner, we achieve efficient anagram checking with reduced complexity, considering both the $O(m\log m)$ character sorting for each word and the $O(n)$ comparison for $n$ words.

Introduction

Problem 1: Unique Echo

Problem 1: Naive Approach

Problem 1: Efficient Approach

Join the 1M+ learners on CodeSignal

Problem 2: Anagram Matcher

Problem 2: Efficient Approach

Problem 2: Solution Building

Lesson Summary