Start learning free

LESSON 257 OF 410 · HASH TABLE

Ransom Note in Java with O(n + m) Time Complexity

Practice O(n + m) Read the full explanation

Given two strings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input:  ransomNote = "aa", magazine = "abb"
Output:  false

Example 2:

Input:  ransomNote = "aa", magazine = "aab"
Output:  true

Note:

Your algorithm should run in O(n + m) time and use O(Σ) extra space.


Hints:

Let's take the two examples given in the statement and solve them "by hand". In both examples, ransomNote consists of two 'a's. Which means we need to have at least two 'a's in magazine to be able to construct the solution. In the first example, we have only one 'a' in magazine and that's why we return false while in the second example, we have two of them, so that's why we return true. Pretty simple. Now what if ransomNote also contains letter 'b'? What property should be satisfied to return true? Take some small examples on paper and try to figure it out.

Let's take ransomNote = "abba". We need at least two 'a's and two 'b's in magazine to be able to construct the solution. First observation is that the order of letters in ransomNote is not important. The requirement is the same also for ransomNote = "aabb" or ransomNote = "abba". The same holds true for magazine. It doesn't matter if magazine = "aaabbb" or magazine = "ababab", both are good as the conditions are satisfied:
  • 'a' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)
  • 'b' occurs in magazine at least the same number of times it does in ransomNote (3 >= 2)
All these being said, can you figure out what condition should be satisfied to return true for the general case?

The condition is that for each letter of the alphabet (from 'a' to 'z'), the letter should appear in magazine at least the same number of times it does in ransomNote. So we need to separately count the number of occurrences of each letter in magazine and in ransomNote. How can we achieve this?

We have a data structure specially designed to do that: a frequency table, such as a Hash Map (or, since the letters are only 'a' to 'z', a 26-slot array). We can build two frequency tables:
  • one for ransomNote, where the entry for letter c is the number of occurrences of c in ransomNote
  • one for magazine, where the entry for letter c is the number of occurrences of c in magazine
How should we populate these tables?

Using a loop, we will go through every character c of ransomNote and increment the entry for c in its table. We will do the same for magazine. What should we do after we have populated these tables?

Using a loop, we should go through each character c of the alphabet (from 'a' to 'z') and check if the count of c in ransomNote is greater than its count in magazine. If so, we should return false. When this loop terminates, we can conclude that the solution is valid, so we can return true

STEP 1 OF 8
    Ctrl + Enter to check

    JAVA · HASH TABLE

    Ransom Note in Java, explained

    Understanding the Problem

    The core challenge of this problem is to determine if the characters in the ransomNote can be found in the magazine string, considering that each character in the magazine can only be used once. This problem is significant in scenarios where resource allocation and availability need to be checked, such as in inventory management or text processing.

    Approach

    To solve this problem, we need to count the frequency of each character in both the ransomNote and the magazine. We can use a HashMap to store these frequencies. The steps are as follows:

    1. Initialize two HashMaps to store the frequency of characters in ransomNote and magazine.
    2. Populate these HashMaps by iterating through each string.
    3. Compare the frequency of each character in ransomNote with that in magazine.
    4. If any character in ransomNote has a higher frequency than in magazine, return false.
    5. If all characters meet the required frequency, return true.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Create two HashMaps: ransomFreq and magazineFreq.
    2. Iterate through ransomNote and populate ransomFreq.
    3. Iterate through magazine and populate magazineFreq.
    4. For each character in ransomNote, check if its frequency in ransomFreq is greater than in magazineFreq.
    5. If any character fails the check, return false. Otherwise, return true.

    Code Implementation

    import java.util.HashMap;

public class RansomNote {
    public boolean canConstruct(String ransomNote, String magazine) {
        // Create frequency maps for ransomNote and magazine
        HashMap<Character, Integer> ransomFreq = new HashMap<>();
        HashMap<Character, Integer> magazineFreq = new HashMap<>();

        // Populate ransomFreq map
        for (char c : ransomNote.toCharArray()) {
            ransomFreq.put(c, ransomFreq.getOrDefault(c, 0) + 1);
        }

        // Populate magazineFreq map
        for (char c : magazine.toCharArray()) {
            magazineFreq.put(c, magazineFreq.getOrDefault(c, 0) + 1);
        }

        // Check if ransomNote can be constructed from magazine
        for (char c : ransomNote.toCharArray()) {
            if (ransomFreq.get(c) > magazineFreq.getOrDefault(c, 0)) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        RansomNote rn = new RansomNote();
        System.out.println(rn.canConstruct("aa", "abb")); // Output: false
        System.out.println(rn.canConstruct("aa", "aab")); // Output: true
    }
}

    Complexity Analysis

    The time complexity of this solution is O(n + m), where n is the length of ransomNote and m is the length of magazine. This is because we iterate through both strings once to populate the frequency maps and then iterate through ransomNote again to check the frequencies.

    The space complexity is O(Σ), where Σ is the number of unique characters in the alphabet (in this case, 26 for lowercase English letters). This is because we store the frequency of each character in the HashMaps.

    Edge Cases

    Consider the following edge cases:

    • Empty ransomNote: Should return true as no characters are needed.
    • Empty magazine: Should return false if ransomNote is not empty.
    • Characters in ransomNote not present in magazine: Should return false.

    Testing

    To test the solution comprehensively, consider the following test cases:

    System.out.println(rn.canConstruct("", "")); // true
System.out.println(rn.canConstruct("a", "")); // false
System.out.println(rn.canConstruct("", "a")); // true
System.out.println(rn.canConstruct("a", "b")); // false
System.out.println(rn.canConstruct("aa", "aab")); // true
System.out.println(rn.canConstruct("aa", "ab")); // false

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller, manageable parts.
    • Use appropriate data structures to store and manipulate data efficiently.
    • Think about edge cases and how your solution handles them.
    • Practice similar problems to improve your problem-solving skills.

    Conclusion

    In this blog post, we discussed how to solve the "Ransom Note" problem using Java. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills and improving coding proficiency.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free