Ransom Note - LeetCode 383 Solution

Problem Overview

#

The Ransom Note problem from LeetCode asks you to determine if you can construct a ransom note using letters from a magazine.

Problem Statement: Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.

Example:

• Input: ransomNote = "a", magazine = "b"

• Output: false

• Input: ransomNote = "a", magazine = "a"

• Output: true

• Input: ransomNote = "aa", magazine = "ab"

• Output: false

• Input: ransomNote = "aa", magazine = "aab"

• Output: true

Solution Approach

#

C# Solution - Using Dictionary

#

Create a Dictionary to count the frequency of each character in the magazine. Then iterate through the ransom note and check if each required character exists in the dictionary with a count greater than zero. Decrement the count for each character used, and return false if any character is not available or has been exhausted.

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        var charCount = new Dictionary<char, int>();

        foreach(char c in magazine) {
            if(charCount.ContainsKey(c)){
                charCount[c]++;
            }else{
                charCount[c] = 1;
            }
        }

        foreach(char c in ransomNote) {
            if(!charCount.ContainsKey(c) || charCount[c] == 0){
                return false;
            }
            charCount[c]--;
        }

        return true;
    }
}

Time Complexity: O(m + n) - where m is magazine length, n is ransom note length Space Complexity: O(1) - at most 26 lowercase letters in the dictionary

Key Insights

#

1. Two-Pass Approach: First pass builds character frequency map, second pass validates construction
2. Character Frequency: Track count of each character in magazine for availability checking
3. Availability Check: Verify both existence and sufficient count before using each character
4. Decrement Usage: Subtract from count when a character is used in ransom note
5. Early Exit: Return false immediately if required character is missing or exhausted
6. Space Efficient: Dictionary size is bounded by alphabet size (26 characters)

Related Problems

#

• Valid Anagram
• Isomorphic Strings
• Majority Element

Video Tutorial

#

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.