Bala Subramanyam LankaBala Lanka
← All posts

LeetCode Question 383: Ransom Note Solution Breakdown

1 min read

SeriesLeetCodepart 6 of 10
  1. LeetCode Problem 1480: Sum
  2. LeetCode Problem 1672: Solving the Richest Customer Wealth Challenge
  3. Leetcode Question 412: Fizz Buzz - My Simple Solution
  4. LeetCode Question 1342: Number of Steps to Reduce a Number to Zero - My Simple Solution
  5. Solving LeetCode Problem 876: Middle of the Linked List
  6. LeetCode Question 383: Ransom Note Solution Breakdown
  7. LeetCode 977: Squares of a Sorted Array Solution
  8. LeetCode 1295: Find Numbers with Even Number of Digits
  9. LeetCode 485 - Finding Max Consecutive Ones
  10. Is Bitwise & Better than Arithmetic to Determine Even or Odd? Let’s Dive In!
On this page

Problem Statement

The problem states:

Given two strings ransomNote and magazine, return true if you can construct the ransomNote from the magazine and false otherwise.

Each letter in the magazine can only be used once in the ransomNote.

So, if you’re wondering whether you have enough letters in the magazine to create a ransom note, this is the problem that will help you check!

My Solution

After scratching my head for a bit (and sipping on some of that sweet, sweet coffee), I came up with a solution in Java. Here’s the code I submitted:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> magazineLetter = new HashMap<>();

        // Count each letter's occurrences in the magazine
        for (int i = 0; i < magazine.length(); i++) {
            char m = magazine.charAt(i);
            int currentCount = magazineLetter.getOrDefault(m, 0);
            magazineLetter.put(m, currentCount + 1);
        }

        // Check each letter in the ransom note
        for (int i = 0; i < ransomNote.length(); i++) {
            char r = ransomNote.charAt(i);
            int currentCount = magazineLetter.getOrDefault(r, 0);
            if (currentCount == 0) {
                return false; // Not enough letters
            }
            magazineLetter.put(r, currentCount - 1); // Use one letter
        }

        return true; // Successfully constructed the ransom note
    }
}

Complexity Analysis

  • Time Complexity: O(m + n), where m is the length of the magazine and n is the length of the ransomNote. We traverse both strings linearly, so this is pretty efficient.

  • Space Complexity: O(1) in terms of the character set size, since we’re only using a fixed-size HashMap for the alphabet (assuming we’re only dealing with standard English letters).

So yeah, overall it’s a pretty neat and efficient solution!

Conclusion

And there you have it, folks. I just walked you through my thought process and solution for LeetCode problem 383. If you’re diving into the world of algorithms and data structures, it’s super important to keep practicing, and I’m here to document my grind.

Feel free to hit me up with your own solutions or questions in the comments. Let’s keep this programming journey rolling!

References

esc