algoadvance

Leetcode 383. Ransom Note

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.

Clarifying Questions

  1. Are the inputs case-sensitive?
    • Yes, the inputs are case-sensitive. For example, ‘a’ and ‘A’ are considered different characters.
  2. Can the ransomNote and magazine be empty strings?
    • Yes, both strings can be empty. If ransomNote is empty, return true because it trivially requires no letters.
  3. What is the maximum length of the ransomNote and magazine?
    • In general practice problems, you can assume they won’t exceed around (10^5) characters.

Strategy

  1. Frequency Counting Method:
    • Construct a frequency count of each character in magazine.
    • Traverse through ransomNote and check if each character is available in the frequency count constructed from magazine.
    • Decrease the frequency for each letter used. If a letter from ransomNote cannot be matched against the frequency count derived from magazine, return false.
    • If all characters in ransomNote can be matched while respecting their frequencies, return true.

Time Complexity

Code

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charCount = new int[26]; // Frequency array for letters 'a' to 'z'
        
        // Populate the frequency array with counts from magazine
        for (char c : magazine.toCharArray()) {
            charCount[c - 'a']++;
        }
        
        // Check each character in ransomNote
        for (char c : ransomNote.toCharArray()) {
            if (--charCount[c - 'a'] < 0) {
                return false; // If usage of any character exceeds its availability
            }
        }
        
        return true; // All characters are available with sufficient frequency
    }
}

Explanation

  1. Frequency Array Construction:
    • charCount array is used to store the count of each character in the magazine. Since there are 26 lowercase English letters, the array size is 26.
  2. Character Check:
    • For each character in ransomNote, we decrement the corresponding count in charCount.
    • If at any point, the count becomes negative, it means the character is used more times than it appears in magazine, hence we return false.
  3. Return True:
    • If we manage to process the entire ransomNote without finding any character overused, we return true.

This approach ensures an efficient determination of whether ransomNote can be constructed from magazine.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI