Problem overview
The function can_construct receives two strings, ransom_note and magazine. It returns true when the note can be built from letters of the magazine, where each magazine letter can be used at most once, and false otherwise. The order of the letters doesn't matter, only how many of each there are.
With ransom_note = "aa" and magazine = "abb" the magazine holds a single a, but the note needs two, so the answer is false. With magazine = "aab" there are two as, so the answer is true. The extra b is simply left unused.
The lesson asks for O(n + m) time, where n and m are the two lengths, and extra space that depends only on the size of the alphabet, not on the input.
Approach: count letters, then spend them
A brute-force version would take each letter of the note and search the magazine for an unused copy, which costs O(n * m). The faster idea is to count first. The note can be built exactly when, for every letter, the magazine has at least as many copies as the note needs.
That suggests a frequency table: how many times each letter occurs. A hash map would work, but the letters here are lowercase English ones, so there are only 26 possible keys. A fixed array of 26 counters is simpler and faster: slot 0 is a, slot 1 is b, and so on. Its size is a constant, which meets the space limit.
The solution uses one table instead of two. It first adds every letter of the magazine to the table, so each slot says how many copies are available. Then it removes the letters the note needs one by one. If any slot goes below zero, the magazine ran out of that letter.
On ransom_note = "aa" and magazine = "abb": after the first loop the table holds a: 1, b: 2. The note's first a brings slot 0 to 0, which is fine. The second a brings it to -1, so the function returns false immediately.
Step by step
- Create the table: an array of 26 zeros of type
i32, declaredmutbecause the counts change. - Loop over the magazine's bytes, with the loop variable
c. - Map each byte to a slot. Subtracting
b'a'turns'a'..='z'into0..=25, and the cast tousizemakes it usable as an index. Add one to that slot. - Loop over the note's bytes the same way.
- Compute the index
idxfor the current letter. - Spend one copy by decrementing
counts[idx]. - Check for a shortage. A negative count means the note used more of this letter than the magazine supplied, so return
falseat once. - Return
trueafter the loop. Reaching the end means no letter ran short.
The solution in Rust
impl Solution {
fn can_construct(ransom_note: String, magazine: String) -> bool {
let mut counts = [0i32; 26];
for c in magazine.bytes() {
counts[(c - b'a') as usize] += 1;
}
for c in ransom_note.bytes() {
let idx = (c - b'a') as usize;
counts[idx] -= 1;
if counts[idx] < 0 {
return false;
}
}
true
}
}
Rust details worth knowing:
- Array repetition.
[0i32; 26]builds an array of 26 copies of0i32. The length is part of the type and fixed at compile time, and the array lives on the stack. - Bytes, not characters.
bytes()yields eachu8of the string's UTF-8 encoding. For lowercase ASCII letters, one byte is one letter.chars()would also work, butbytes()gives numbers that are easy to subtract. - Byte literals.
b'a'is au8with the value 97. Bothcandb'a'areu8, so the subtraction is au8subtraction, and the result is converted withas usize. - Bounds-checked indexing.
counts[idx]panics ifidxis 26 or more, instead of reading unrelated memory. - The final expression.
truewithout a semicolon is the value of the function.
Complexity
Time: O(n + m). The first loop visits each of the m magazine bytes once, and the second visits each of the n note bytes at most once. Each step is a constant-time array update.
Space: O(1), or O(Σ) where Σ is the alphabet size. The table has 26 slots no matter how long the strings are.
Edge cases and common mistakes
- Empty note. Nothing needs to be built, so the second loop never runs and the answer is
true, even for an empty magazine. - Empty magazine, non-empty note. The first letter of the note brings its slot to -1, so the answer is
false. - Magazine shorter than the note. This can never succeed, and the loop finds out by the time it runs out of copies.
- Checking only that letters exist. Seeing each note letter somewhere in the magazine isn't enough:
"aa"against"abb"has anabut only one. The counts are what matter. - Letters outside
atoz. The table only has room for 26 lowercase letters. For an uppercaseA, the byte 65 minus 97 doesn't go negative: in the optimized build the lessons use, theu8subtraction wraps to 224, and indexing slot 224 panics with an out-of-bounds error. In a debug build the subtraction itself panics. Code that must accept other characters needs a bigger table (256 slots indexed by the byte) or aHashMap. - Counting the note first. That works as well, with the check done in a final pass over the table, but the version above can stop early.
Testing
ransom_note = "aa",magazine = "abb"givesfalse.ransom_note = "aa",magazine = "aab"givestrue.ransom_note = "abba",magazine = "ababab"givestrue.ransom_note = "",magazine = "abc"givestrue.ransom_note = "a",magazine = ""givesfalse.
