Ransom notes and more in Java

Photo by Annie Spratt on Unsplash

Solving coding challenges is an important aspect of a software engineer’s development as it helps to improve several important skills. Coding challenges help to enhance problem-solving skills by requiring engineers to think critically and creatively to find solutions to real-world problems. They also help to improve technical skills by exposing engineers to new technologies and programming concepts, and allowing them to gain experience working with these technologies in a controlled environment. Additionally, coding challenges provide a platform for engineers to showcase their skills to potential employers and demonstrate their ability to solve complex problems. Finally, they provide a way for engineers to learn from others by reviewing their code and understanding how they approached the problem.

The given code is a Java solution to a coding challenge, which checks if it’s possible to construct a ransom note using the letters from a magazine. The challenge requires taking two strings as input, ransomNote and magazine, and returning a boolean indicating whether or not the ransom note can be constructed using the letters from the magazine.

package com.app;

import java.util.HashMap;

public class E01 {
    /**
     * Given two strings ransomNote and magazine,
     * return true if ransomNote can be constructed by using the letters from magazine
     * and false otherwise.
     *
     * @param ransomNote - string #1
     * @param magazine - string #2
     * @return boolean
     */
    public static boolean canConstruct(String ransomNote, String magazine) {

        HashMap<Character, Integer> availableChars = new HashMap<>();
        for (char c : magazine.toCharArray()){
            if(!availableChars.containsKey(c)){
                availableChars.put(c, 1);
            } else {
                Integer currentValue = availableChars.get(c);
                availableChars.put(c, currentValue += 1);
            }
        }

        for (char c : ransomNote.toCharArray()) {
            if(!availableChars.containsKey(c) || availableChars.get(c) == 0) return false;
            Integer currentValue = availableChars.get(c);
            availableChars.put(c, currentValue -= 1);
        }

        return true;
    }
}

The code uses a HashMap to store the frequency of each character in the magazine. It loops through each character in the magazine, incrementing the frequency of the character in the HashMap. Then, it loops through each character in the ransom note, checking if the character is present in the HashMap and its frequency is greater than 0. If the frequency is 0 or the character is not present in the HashMap, the function returns false.

Let’s take an example to understand how the code works. Consider the ransom note is “attack” and the magazine is “atacktwithme”. The code will start by creating a HashMap to store the frequency of each character in the magazine, which would look like this: {a: 2, t: 2, c: 1, k: 1, w: 1, i: 1, h: 1, m: 1, e: 1}.

Next, the code will loop through each character in the ransom note. For the first character “a”, it is present in the HashMap, and its frequency is decremented by 1 to 1. The next character “t” is also present in the HashMap, and its frequency is decremented by 1 to 1. The code then repeats this process for each character in the ransom note. If the loop for the ransom note completes without returning false, the function returns true, indicating that it is possible to construct the ransom note using the letters from the magazine. In this example, the function would return true, meaning that the ransom note “attack” can be constructed using the letters from the magazine “atacktwithme”.

The code has a time complexity of O(n + m) and a space complexity of O(m), where n is the length of the ransomNote string and m is the length of the magazine string. The reason for this is that we are looping through each character of both ransomNote and magazine strings, hence the O(n + m) time complexity. The HashMap used to store the frequency of each character in the magazine string takes up O(m) space as in the worst case scenario, all the characters in the magazine string are unique, meaning the HashMap will have m key-value pairs.

In conclusion, the code solves the challenge by using a HashMap to store the frequency of each character in the magazine and using it to check if the ransom note can be constructed using the letters from the magazine.

I regularly share similar content relating to tech and programming. Give my account a follow to keep up to date with my new publications!