Scale Engineer

Ransom Note

Easy
#0370Time: 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.4 companies
Patterns
Counting
Data structures
Hash TableString
Companies
CriteoKaratSpotifyDisney

Prompt

[Fetch error]

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem