Problem Statement

You are given two strings:

• ransomNote – the note you want to write.
• magazine – the letters you have available.

You need to check if you can construct the ransomNote using the letters from magazine. Each letter in magazine can only be used once.

Example:

Input: ransomNote = "a", magazine = "b"
Output: false
Explanation: You cannot form "a" from "b".

Input: ransomNote = "aa", magazine = "aab"
Output: true
Explanation: You can form "aa" using two 'a's from "aab".

Constraints:

• Only lowercase English letters are used.

---

Approach to Solve the Problem (Simple Language)

1. Count letters in magazine: Keep track of how many times each letter appears in magazine.
2. Check letters in ransomNote: For each letter in ransomNote, check if it is available in the magazine count.
3. Use letters carefully: If a letter from ransomNote is available, reduce its count by 1 (because each letter can be used once).
4. Return result: If any letter in ransomNote is not available in magazine, return false. Otherwise, return true.

Optimized Idea:

• Since the problem uses only lowercase letters, we can use an array of size 26 to store letter counts.
• This makes lookups and updates O(1).

Steps in short:

1. Create an array count[26] to store letters from magazine.
2. For each character c in magazine, increment count.
3. For each character c in ransomNote, check count:
   • If count > 0, decrement it.
   • If count == 0, return false.
4. If all letters are available, return true.

---

Java Code Solution

public class RansomNote {

    public static boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26]; // Array to store count of letters in magazine

        // Count letters in magazine
        for (char c : magazine.toCharArray()) {
            count++;
        }

        // Check if ransomNote can be constructed
        for (char c : ransomNote.toCharArray()) {
            if (count == 0) {
                return false; // Letter not available
            }
            count--; // Use the letter
        }

        return true; // All letters available
    }

    public static void main(String[] args) {
        String ransomNote = "aa";
        String magazine = "aab";
        boolean result = canConstruct(ransomNote, magazine);
        System.out.println("Can construct ransom note: " + result); // Output: true
    }
}

---

Dry Run Example

Input:

ransomNote = "aa"
magazine = "aab"

Step-by-step Execution:

1. Initialize count array for magazine:

magazine letters: a a b
count['a' - 'a'] = 2
count['b' - 'a'] = 1

Array representation (letters a to z):

count = [2, 1, 0, 0, 0, ..., 0]

2. Iterate through ransomNote = "aa":

• First ‘a’: count[0] = 2 → decrement → count[0] = 1
• Second ‘a’: count[0] = 1 → decrement → count[0] = 0

3. All letters found → return true.

---

Textual Diagram for Understanding

magazine: a a b
ransomNote: a a

Step 1: Count letters in magazine
a -> 2
b -> 1

Step 2: Check ransomNote letters
a -> count > 0 -> decrement -> 1 left
a -> count > 0 -> decrement -> 0 left

All letters available -> true

---

Complexity Analysis

• Time Complexity: O(m + n)
  • m = length of magazine, n = length of ransomNote.
  • O(m) to count magazine letters, O(n) to check ransomNote.
• Space Complexity: O(1)
  • The count array is fixed size (26), so constant space.

---

This approach is efficient, simple, and leverages the fact that only lowercase letters are involved.