Mastering Unique Elements and Anagram Detection with Kotlin HashSet

Welcome to our focused exploration of Kotlin's HashSet and its remarkable applications in solving algorithmic challenges. In this lesson, "Mastering Unique Elements and Anagram Detection with Kotlin HashSet," we'll delve into how this efficient data structure can be leveraged to address and solve various types of problems commonly encountered in technical interviews.

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

A basic approach would involve counting occurrences of each word by scanning the entire array for each word, resulting in an O(n^2) time complexity.

Here is the naive approach in Kotlin:

fun findLastUniqueWordNaive(words: Array<String>): String? {
    // Iterate from the end of the array
    for (i in words.indices.reversed()) {
        val currentWord = words[i]
        var count = 0
        
        // Count occurrences of the current word
        for (word in words) {
            if (word == currentWord) {
                count++
            }
        }
        
        // If the word appears exactly once, it's unique
        if (count == 1) {
            return currentWord
        }
    }
    
    return null // No unique word found
}

In this naive implementation, we iterate backwards through the array and for each word, we scan the entire array to count its occurrences. The first word we encounter with a count of 1 is our last unique word.

We can utilize two HashSet<String> instances: wordsSet to maintain unique words and duplicatesSet to keep track of duplicate words. By the end, we can remove all duplicated words from wordsSet to achieve our goal. Here's how to use HashSet to solve the problem in Kotlin:

Create a HashSet instance to store unique words:

val wordsSet: HashSet<String> = hashSetOf()

Initialize another HashSet to monitor duplicates:

val duplicatesSet: HashSet<String> = hashSetOf()

Iterate through the word array, filling wordsSet and duplicatesSet:

for (word in words) {
    if (wordsSet.contains(word)) {
        duplicatesSet.add(word)
    } else {
        wordsSet.add(word)
    }
}

Use the removeAll method from the HashSet API to remove all duplicated words from wordsSet:

wordsSet.removeAll(duplicatesSet)

Now, wordsSet only contains unique words. Find the last unique word by iterating through the original word list from the end:

var lastUniqueWord: String? = null
for (i in words.indices.reversed()) {
    if (wordsSet.contains(words[i])) {
        lastUniqueWord = words[i]
        break
    }
}

And finally, return the last unique word:

fun findLastUniqueWordEfficient(words: Array<String>): String? {
    val wordsSet: HashSet<String> = hashSetOf()
    val duplicatesSet: HashSet<String> = hashSetOf()

    for (word in words) {
        if (wordsSet.contains(word)) {
            duplicatesSet.add(word)
        } else {
            wordsSet.add(word)
        }
    }

    wordsSet.removeAll(duplicatesSet)

    var lastUniqueWord: String? = null
    for (i in words.indices.reversed()) {
        if (wordsSet.contains(words[i])) {
            lastUniqueWord = words[i]
            break
        }
    }

    return lastUniqueWord
}

This efficient approach, with a time complexity close to O(n), is far superior to the naive method and showcases your proficiency in solving algorithmic problems with Kotlin's HashSet.