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 dictionary to store the frequency of each character in the magazine. This allows for efficient lookup of character counts.

2. Check ransom note characters: Iterate through the ransomNote. For each character:

   • Check if it exists in the frequency map. If not, return false (because the character isn't in the magazine).
   • If it exists, decrement its count in the map. If the count becomes 0, remove the character from the map.

3. Return true if all characters are found: If the loop completes without returning false, it means all characters in ransomNote were found in magazine with sufficient frequency. Return true.

Explanation

The solution uses a frequency counting approach. Instead of repeatedly searching the magazine string for each character in the ransomNote, we build a frequency map of the magazine upfront. This improves efficiency, especially for larger inputs. The time complexity becomes linear with respect to the lengths of the input strings.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        // Create a frequency map for the magazine
        Dictionary<char, int> magazineFreq = new Dictionary<char, int>();
        foreach (char c in magazine) {
            if (magazineFreq.ContainsKey(c)) {
                magazineFreq[c]++;
            } else {
                magazineFreq[c] = 1;
            }
        }

        // Check if ransomNote can be constructed
        foreach (char c in ransomNote) {
            if (!magazineFreq.ContainsKey(c) || magazineFreq[c] == 0) {
                return false; // Character not found or count is 0
            }
            magazineFreq[c]--; 
        }

        return true; // All characters found
    }
}

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.
• Space Complexity: O(k), where k is the number of unique characters in magazine. The space used is proportional to the size of the frequency map. In the worst case, k could be equal to n (if all characters are unique).