Ransom Note easy

Problem Statement

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 = "a", magazine = "b" Output: false

Example 2

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

Steps

1. Create a frequency map: We'll use a HashMap to store the frequency of each character in the magazine string. This allows us to efficiently check if we have enough occurrences of each character in the magazine to form the ransomNote.

2. Iterate through the ransomNote: We'll iterate through each character in the ransomNote.

3. Check frequency: For each character, we'll check its frequency in the HashMap created in step 1.

4. Decrement frequency: If the character exists in the HashMap and its frequency is greater than 0, we'll decrement its frequency. Otherwise, we immediately know we can't construct the ransom note.

5. Return true/false: After iterating through all characters in ransomNote, if we haven't encountered any character with insufficient frequency, we return true. Otherwise, we return false.

Explanation

The HashMap provides an efficient way to count character frequencies. Instead of iterating through the magazine string repeatedly for each character in ransomNote, we preprocess the magazine once to build the frequency map. This significantly reduces time complexity. The subsequent character checks in the ransomNote become O(1) on average thanks to HashMap's constant time lookup.

Code

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> magazineFreq = new HashMap<>();

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

        // Check if ransomNote can be constructed
        for (char c : ransomNote.toCharArray()) {
            if (!magazineFreq.containsKey(c) || magazineFreq.get(c) == 0) {
                return false;
            }
            magazineFreq.put(c, magazineFreq.get(c) - 1);
        }

        return true;
    }
}

Complexity

• Time Complexity: O(m + n), where m is the length of ransomNote and n is the length of magazine. We iterate through both strings once. HashMap operations (get, put) are on average O(1).

• Space Complexity: O(k), where k is the number of unique characters in the magazine. In the worst case, k could be equal to the length of the magazine if all characters are unique. This space is used to store the HashMap.