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 counter for the magazine string: This will store the count of each character in magazine. We can use a dictionary for this.

2. Iterate through the ransomNote string: For each character in ransomNote, check if it exists in the frequency counter.

3. Check frequency: If the character exists, decrement its count in the frequency counter. If the count becomes 0, remove the character from the counter.

4. Handle missing characters: If a character from ransomNote is not found in the frequency counter (or its count is already 0), return False immediately, as we cannot construct the ransomNote.

5. Return True if successful: If the loop completes without finding any missing characters, it means we can construct ransomNote from magazine, so return True.

Explanation

The solution leverages the idea of frequency counting. By tracking the frequency of characters in the magazine, we can efficiently check if we have enough of each character to build the ransomNote. Using a dictionary for the frequency counter allows for O(1) lookup time for character counts. This makes the overall algorithm quite efficient.

Code

from collections import Counter

def canConstruct(ransomNote, magazine):
    """
    Checks if ransomNote can be constructed from magazine.

    Args:
        ransomNote: The string to be constructed.
        magazine: The string containing available characters.

    Returns:
        True if ransomNote can be constructed, False otherwise.
    """
    mag_count = Counter(magazine)  # Create frequency counter for magazine

    for char in ransomNote:
        if char not in mag_count or mag_count[char] == 0:
            return False  # Character not found or count is 0
        mag_count[char] -= 1  # Decrement count

    return True  # All characters found


# Example usage
ransomNote1 = "a"
magazine1 = "b"
print(f"Can construct '{ransomNote1}' from '{magazine1}': {canConstruct(ransomNote1, magazine1)}")  # Output: False

ransomNote2 = "aa"
magazine2 = "aab"
print(f"Can construct '{ransomNote2}' from '{magazine2}': {canConstruct(ransomNote2, magazine2)}")  # Output: True

ransomNote3 = "aa"
magazine3 = "aba"
print(f"Can construct '{ransomNote3}' from '{magazine3}': {canConstruct(ransomNote3, magazine3)}") #Output: False

Complexity

• Time Complexity: O(m + n), where 'm' is the length of ransomNote and 'n' is the length of magazine. Creating the counter is O(n), and iterating through ransomNote is O(m). Dictionary lookups are O(1) on average.

• Space Complexity: O(min(m, n)), The space used by the mag_count dictionary is at most the size of the smaller string's unique characters (because it's a frequency counter). In the worst-case scenario, all characters are unique, resulting in this space complexity.