Logo

Kode$word

Ransom Note – Frequency Counting Made Simple (LeetCode 383)
Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Ransom Note – Frequency Counting Made Simple (LeetCode 383)

Using HashMap to Validate Character Availability Efficiently

21 views
0
0
HashMapStringFrequency CountGreedyLeetCodeEasy
Github icon

🔗 Problem Link

LeetCode 383 – Ransom Note

👉 https://leetcode.com/problems/ransom-note/

Introduction

This is a classic frequency-count problem that tests your understanding of:

  1. Character counting
  2. HashMap usage
  3. Greedy validation logic

At first glance, the problem looks very simple — but it’s a very common interview question because it checks whether you can think in terms of resource usage.

Here:

  1. magazine → available resources
  2. ransomNote → required resources

We must check if the available letters are sufficient to construct the ransom note.

📌 Problem Understanding

You are given:

  1. ransomNote
  2. magazine

Rules:

  1. Each letter in magazine can be used only once.
  2. Return true if ransomNote can be formed.
  3. Otherwise return false.

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

🧠 Intuition

The logic is straightforward:

  1. Count frequency of each character in magazine.
  2. For each character in ransomNote:
  3. Check if it exists in the map.
  4. Check if its frequency is greater than 0.
  5. Reduce frequency after using it.
  6. If at any point we cannot use a character → return false.

This is a greedy approach.

💻 Your Code

class Solution {
public boolean canConstruct(String r, String m) {
HashMap<Character,Integer> mp = new HashMap<>();
for(int i =0 ; i < m.length();i++){
mp.put(m.charAt(i),mp.getOrDefault(m.charAt(i),0)+1);
}
for(int i = 0 ; i <r.length();i++){
if(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0){
mp.put(r.charAt(i),mp.get(r.charAt(i)) -1);
}else{
return false;
}
}
return true;
}
}

🔍 Step-by-Step Explanation

1️⃣ Build Frequency Map from Magazine

HashMap<Character,Integer> mp = new HashMap<>();
for(int i =0 ; i < m.length();i++){
mp.put(m.charAt(i), mp.getOrDefault(m.charAt(i),0) + 1);
}

We count how many times each character appears in the magazine.

2️⃣ Check Each Character in Ransom Note

for(int i = 0 ; i < r.length();i++){

For every character in ransomNote:

3️⃣ Validate Availability

if(mp.containsKey(r.charAt(i)) && mp.get(r.charAt(i)) > 0)

If:

  1. Character exists in map
  2. Frequency is still available

Then reduce its count:

mp.put(r.charAt(i), mp.get(r.charAt(i)) - 1);

Otherwise:

return false;

Immediately stop if we cannot construct.

🎯 Why This Works

We treat:

  1. magazine as supply
  2. ransomNote as demand

We reduce supply every time we use a character.

If supply runs out → construction fails.

⏱ Complexity Analysis

Time Complexity: O(n + m)

  1. One pass to build map from magazine
  2. One pass to check ransomNote

Space Complexity: O(26) ≈ O(1)

Only lowercase English letters.

🔥 Even Better Optimization – Using Array Instead of HashMap

Since we know:

  1. Only lowercase letters are allowed

We can use an integer array of size 26.

This is faster and more memory-efficient.

Optimized Version

class Solution {
public boolean canConstruct(String r, String m) {
int[] freq = new int[26];

for(char c : m.toCharArray()){
freq[c - 'a']++;
}

for(char c : r.toCharArray()){
if(freq[c - 'a'] == 0){
return false;
}
freq[c - 'a']--;
}

return true;
}
}

This avoids HashMap overhead.

🏁 Final Thoughts

This problem reinforces:

  1. Frequency counting pattern
  2. Greedy character usage
  3. Early exit for optimization
  4. Using arrays instead of HashMap when character set is limited

It’s a foundational problem that appears often in interviews.

If you master this pattern, you can easily solve:

  1. Valid Anagram
  2. Find the Difference
  3. Check if All Characters Have Equal Occurrences
  4. Permutation in String


Related Articles

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Check if All Characters Have Equal Number of Occurrences – Frequency Map Approach (LeetCode 1941)

Simple HashMap Technique to Validate Equal Character Frequencies

Read Article
Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Longest Palindrome – Building the Maximum Length from Given Letters (LeetCode 409)

Using Frequency Counting to Construct the Largest Possible Palindrome

Read Article
Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Valid Anagram – Frequency Counting Pattern Explained (LeetCode 242)

Using HashMap and Array Optimization to Detect Anagrams Efficiently

Read Article
Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

Reverse Vowels of a String – From Extra Space Approach to Two Pointer Optimization (LeetCode 345)

Understanding Different Ways to Reverse Only Vowels Efficiently

Read Article

Ai Assistant Kas