# Ransom Note
**Difficulty:** EASY
[External](https://leetcode.com/problems/ransom-note)
Canonical: https://scaleengineer.com/dsa/problems/ransom-note
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Criteo](https://scaleengineer.com/companies/criteo), [Karat](https://scaleengineer.com/companies/karat), [Spotify](https://scaleengineer.com/companies/spotify), [Disney](https://scaleengineer.com/companies/disney)
---
## Problem
\[Fetch error\]

# Approaches
## Brute Force Simulation
This approach directly simulates the process of constructing the ransom note. For each character required by the ransom note, we search for it in the magazine. If found, we mark it as used to prevent it from being used again.
**Time:** O(n * m), where n is the length of the `ransomNote` and m is the length of the `magazine`. For each of the n characters in the ransom note, we might have to scan the entire magazine of length m to find it. · **Space:** O(m), where m is the length of the magazine. This is because we need a mutable copy of the magazine string (e.g., a `StringBuilder`) to mark characters as used.
**Pros:** Simple to conceptualize and implement.; Doesn't require any advanced data structures.
**Cons:** Highly inefficient, with a time complexity that is quadratic in the lengths of the strings.; Performs poorly on large inputs due to the nested search operation.
### Explanation
The algorithm iterates through every character of the `ransomNote`. For each character, it searches for a corresponding match in the `magazine`. To ensure that each letter from the `magazine` is used only once, we must 'consume' the character from the `magazine` once it's used. A simple way to do this is to convert the `magazine` string into a more flexible data structure like a `StringBuilder`. When a character is found, we can delete it from the structure. If at any point we cannot find a required character for the `ransomNote`, we know it's impossible to construct, and we return `false`. If we successfully find and consume a character from the `magazine` for every character in the `ransomNote`, we return `true`.

```java
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        StringBuilder magazineBuilder = new StringBuilder(magazine);
        for (char c : ransomNote.toCharArray()) {
            int index = magazineBuilder.indexOf(String.valueOf(c));
            if (index == -1) {
                return false;
            }
            magazineBuilder.deleteCharAt(index);
        }
        return true;
    }
}
```
### Algorithm
- Convert the `magazine` string to a mutable data structure like a `StringBuilder`.
- Iterate through each character `c` of the `ransomNote`.
- For each `c`, search for its first occurrence in the `magazine` structure.
- If `c` is found at index `i`, remove it to mark it as used (e.g., `magazine.deleteCharAt(i)`).
- If `c` is not found, it's impossible to form the note, so return `false`.
- If the loop completes successfully, it means all characters were found, so return `true`.

## Sorting and Two Pointers
A more optimized approach involves sorting both the ransom note and the magazine. Once sorted, we can use a two-pointer technique to efficiently check if all characters of the ransom note can be found in the magazine in the correct quantities.
**Time:** O(m log m + n log n), where n and m are the lengths of the `ransomNote` and `magazine` respectively. The dominant operation is sorting the two strings. The subsequent two-pointer scan takes O(n + m) time. · **Space:** O(n + m) in Java. Strings are immutable, so `toCharArray()` creates copies of size n and m. The space used by the sorting algorithm itself is typically O(log n) or O(log m) for primitive types.
**Pros:** Significantly more efficient than the brute-force approach.; Logically straightforward after the sorting step.
**Cons:** The time complexity is dominated by sorting, which is not as fast as the linear-time hash map approach.; Requires extra space to hold the character arrays for sorting.
### Explanation
This method leverages the power of sorting to simplify the comparison. By sorting both the `ransomNote` and `magazine` strings alphabetically, we can check for the availability of characters in a single pass using two pointers. We maintain one pointer for the `ransomNote` and one for the `magazine`. We advance the pointers based on character comparison. If the `magazine` character is smaller than the `ransomNote` character, we move to the next character in the `magazine` to find a potential match. If they are equal, we've found a match for the current `ransomNote` character, so we advance both pointers. If the `magazine` character is larger, it means we've skipped past the required character in the sorted `magazine`, so a match is impossible.

```java
import java.util.Arrays;

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        char[] noteChars = ransomNote.toCharArray();
        char[] magChars = magazine.toCharArray();
        
        Arrays.sort(noteChars);
        Arrays.sort(magChars);
        
        int notePtr = 0;
        int magPtr = 0;
        
        while (notePtr < noteChars.length && magPtr < magChars.length) {
            if (magChars[magPtr] < noteChars[notePtr]) {
                magPtr++;
            } else if (magChars[magPtr] == noteChars[notePtr]) {
                notePtr++;
                magPtr++;
            } else { // magChars[magPtr] > noteChars[notePtr]
                return false;
            }
        }
        
        return notePtr == noteChars.length;
    }
}
```
### Algorithm
- Convert both `ransomNote` and `magazine` to character arrays.
- Sort both character arrays alphabetically.
- Initialize two pointers, `i` for the `ransomNote` array and `j` for the `magazine` array, both starting at 0.
- While both pointers are within their respective array bounds:
  - If `magazine[j] < ransomNote[i]`, we need a larger character from the magazine, so increment `j`.
  - If `magazine[j] == ransomNote[i]`, we found a match. Increment both `i` and `j`.
  - If `magazine[j] > ransomNote[i]`, it means the character `ransomNote[i]` is not available in the magazine, so return `false`.
- After the loop, if pointer `i` has traversed the entire `ransomNote` array, it means all characters were found. Return `true`.

## Frequency Counter (Hash Map / Array)
The most efficient approach uses a frequency counter to solve the problem in linear time. The idea is to count the occurrences of each character in the magazine. Then, we iterate through the ransom note and check if each required character is available in sufficient quantity.
**Time:** O(n + m), where n is the length of the `ransomNote` and m is the length of the `magazine`. We perform a single pass over the magazine to build the frequency map and a single pass over the ransom note to check for characters. · **Space:** O(k), where k is the number of possible characters in the character set (the alphabet size). If the problem is constrained to lowercase English letters, k=26, making the space complexity constant, O(1).
**Pros:** Optimal time complexity (linear).; Very efficient for large inputs.; Constant space complexity if the character set is fixed.
**Cons:** Requires extra space for the frequency map, although it's typically small and constant for a fixed alphabet.
### Explanation
This is the most optimal approach. The problem is fundamentally about character frequencies: for every character `c`, its frequency in `ransomNote` must be less than or equal to its frequency in `magazine`. We can efficiently track these frequencies using a hash map or, even better, a simple array if the character set is limited (e.g., 26 lowercase English letters).
First, we iterate through the `magazine` string and populate our frequency counter. Then, we iterate through the `ransomNote`. For each character in the note, we decrement its count in our frequency array. If we ever try to decrement a count that is already zero, it means the `magazine` did not have enough of that character, so we can immediately return `false`. If we successfully process all characters in the `ransomNote`, it means it can be constructed, and we return `true`.

```java
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        
        int[] counts = new int[26]; // For lowercase English letters
        
        // Count characters in magazine
        for (char c : magazine.toCharArray()) {
            counts[c - 'a']++;
        }
        
        // Check if ransomNote can be constructed
        for (char c : ransomNote.toCharArray()) {
            if (counts[c - 'a'] == 0) {
                return false; // Not enough characters
            }
            counts[c - 'a']--;
        }
        
        return true;
    }
}
```
### Algorithm
- Create a frequency counter, such as an integer array of size 26 for lowercase English letters, initialized to zeros.
- Iterate through the `magazine` string. For each character, increment its corresponding count in the frequency array.
- Iterate through the `ransomNote` string.
- For each character `c` in the `ransomNote`:
  - Check the count for `c` in the frequency array. If it's 0, the character is not available. Return `false`.
  - If the count is greater than 0, decrement it to 'use up' the character.
- If the loop over `ransomNote` completes, it means all characters were available in sufficient quantities. Return `true`.

# Solutions
### CSharp

```csharp
public class Solution { public bool CanConstruct ( string ransomNote , string magazine ) { int [] cnt = new int [ 26 ]; foreach ( var c in magazine ) { ++ cnt [ c - 'a' ]; } foreach ( var c in ransomNote ) { if (-- cnt [ c - 'a' ] < 0 ) { return false ; } } return true ; } }
```

### Java

```java
class Solution {
public
  boolean canConstruct(String ransomNote, String magazine) {
    int[] cnt = new int[26];
    for (int i = 0; i < magazine.length(); ++i) {
      ++cnt[magazine.charAt(i) - 'a'];
    }
    for (int i = 0; i < ransomNote.length(); ++i) {
      if (--cnt[ransomNote.charAt(i) - 'a'] < 0) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool canConstruct(string ransomNote, string magazine) {
    int cnt[26]{};
    for (char &c : magazine) {
      ++cnt[c - 'a'];
    }
    for (char &c : ransomNote) {
      if (--cnt[c - 'a'] < 0) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool: cnt = Counter(magazine) for c in ransomNote: cnt[c] -= 1 if cnt[c] < 0: return False return True

```