Ransom note challenge in Kotlin

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines; otherwise, return false.

Each letter in the magazine can only be used once in your ransom note.

Consider this example:

    "a", "b" -> false
    "aa", "ab" -> false
    "aa", "aab" -> true

A quick review of Hashing

In the below solution, we use the hashmap to save the data. For this reason, before presenting the solution it’s important to do a quick review of hashing.

Hashing is used to map data of arbitrary size to data of a fixed size.

A Hash map is a structure that can map keys to values. They use a hash function to intelligently figure out where to store elements. All operations reading, insertion and deletion take a constant amount of time O(1).

If two keys map to the same value, a collision occurs.

A common way to handle collisions is to use chaining. With chaining keys and their values are not stored directly in the array. Each array element is a list of zero or more key/values pairs. In this case, the time for hash map operations is the time to find the bucket (constant time), plus the time to iterate through the list.

The solution

A possible solution is to count the occurrences in the magazine string and save there in an hashmap. After that, cycle on ransom note and decrement the value for each character encountered. If the corresponding value inside the hash is less than zero return false, otherwise return true.

    fun canConstruct(ransomNote: String, magazine: String): Boolean {
        val counts = mutableMapOf<Char, Int>()
        for (c in magazine.toCharArray()) {
            counts[c] = counts.getOrDefault(c, 0) + 1
        }

        for (r in ransomNote.toCharArray()) {
            if (!counts.containsKey(r) || counts[r]!! <= 0) {
                return false
            }
            counts[r] = counts.getOrDefault(r, 0) - 1
        }

        return true
    }

Time and space complexity

• The time complexity is equal to O(m) for magazine string and O(n) for the ransom string. The final result is O(m) + O(n).
• The space complexity is equal to O(n) the space to save the hash in memory.

Before concluding I recommend you to like and share this post and leave a comment. It costs you nothing while it encourages me to continue producing other similar content. Thanks for your support.

See you in the next algorithms. 😉