Vultr DocsLatest Content

Ransom Note

Updated on 04 July, 2025
Ransom Note header image

Problem Statement

The task is to determine whether a given string, ransomNote, can be constructed entirely using the characters from another string, magazine. Each character in magazine may only be utilized once when constructing ransomNote. If it is possible to form the ransomNote from the magazine string, the function should return true, otherwise, it should return false. This problem tests one's ability to manipulate and count characters in strings efficiently under specific constraints.

Examples

Example 1

Input:

ransomNote = "a", magazine = "b"

Output:

false

Example 2

Input:

ransomNote = "aa", magazine = "ab"

Output:

false

Example 3

Input:

ransomNote = "aa", magazine = "aab"

Output:

true

Constraints

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote and magazine consist of lowercase English letters.

Approach and Intuition

To solve this problem, consider the following intuitive approach:

  1. Frequency Counting:

    • Count the frequency of each letter in both ransomNote and magazine.

  2. Comparison of Frequencies:

    • Check if for every character in ransomNote, the frequency of that character in magazine is greater than or equal to its frequency in ransomNote. If at any time this condition is not met, return false.

  3. Return Result:

    • If all characters in ransomNote can be matched with sufficient frequency from magazine, then return true. Otherwise, as checked in the previous step, return false.

The rationale behind this approach is straightforward: a ransomNote can only be constructed from magazine if magazine has at least as many of each required character as ransomNote does. This would mean checking against each unique character's frequency from both strings and ensuring magazine's supply meets or exceeds ransomNote's demand.

Solutions

  • Java
java 
class Solution {
    
    private Stack<Character> organizeCharacters(String str) {
        char[] characters = str.toCharArray();
        Arrays.sort(characters);
        Stack<Character> charStack = new Stack<>();
        for (int i = str.length() - 1; i >= 0; i--) {
            charStack.push(characters[i]);
        }
        return charStack;
    }
        
    public boolean canConstruct(String ransomNote, String magazine) {
            
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
            
        Stack<Character> magazineChars = organizeCharacters(magazine);
        Stack<Character> ransomChars = organizeCharacters(ransomNote);
            
        while (!magazineChars.isEmpty() && !ransomChars.isEmpty()) {
            if (magazineChars.peek().equals(ransomChars.peek())) {
                magazineChars.pop();
                ransomChars.pop();
            } else if (magazineChars.peek() < ransomChars.peek()) {
                magazineChars.pop();
            } else {
                return false;
            }
        }
            
        return ransomChars.isEmpty();
    }
}

This Java solution checks if a ransom note can be constructed from the characters of a magazine, focusing on the order and availability of characters. Here’s a breakdown of the solution approach:

  • Utility Function: The organizeCharacters method takes a string, converts it to an array of its characters, and sorts this array in ascending order. It then creates a Stack, pushing the characters onto the stack in reverse order, thus effectively sorting the characters in descending order in the stack.

  • Construction Function: The canConstruct method checks if the ransom note can be constructed using characters from the magazine:

    1. First, it checks whether the length of the ransom note is greater than the magazine. If true, it immediately returns false since more characters are needed than are available.
    2. It then calls organizeCharacters for both the ransom note and the magazine, storing the returned stacks.
    3. It then enters a loop, checking top characters of both stacks:
      • If the character from both stacks matches, it pops both stacks (using those characters).
      • If the magazine's character is less than the ransom note's character in lexicographical order, the top magazine character is popped and discarded, which denotes that the character cannot be used to match any remaining character of the ransom note.
      • If the magazine's character is greater, it returns false as it is impossible to match the characters successfully.
    4. After exiting the loop, it checks if the ransom note's stack is empty. If empty, true is returned, indicating all characters required for the ransom note were matched and removed.

This approach effectively utilizes stacks and sorting to ensure each character in the ransom note can be matched in sequence from the magazine, ensuring an efficient solution to the problem by minimizing the amount of scanning back and forth through the input strings.

Comments

No comments yet.