Interview Problem Explained: Ransom Note (LeetCode 383, String Manipulation & Counting Array)

Ransom Note: Problem Statement

You are given two strings: ransomNote and magazine.

Your task is to determine whether you can construct the ransomNote using only the characters from magazine. Each character in magazine can only be used once in ransomNote.

Input:

• ransomNote: the target string to construct

• magazine: the source string containing available characters

Constraints:

• Both ransomNote and magazine consist only of lowercase English letters.

• 1 ≤ ransomNote.length, magazine.length ≤ 10⁵

Tip: This is LeetCode Problem 383. Codetree provides clear examples and step-by-step logic to help you fully understand the problem.

Step 1. Understand the Problem with Examples

Let’s start by analysing what it means to say the ransom note “can be constructed” from the magazine string.

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: False

'a' is required, but 'b' is the only character available → cannot construct.

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: False

Two 'a's are required but only one is available.

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: True

Two 'a's are required and available → can construct.

Example 4:

Input: ransomNote = "aabcba", magazine = "abbc"
Output: False

Three 'a's are required but only one is available in magazine.

Example 5:

Input: ransomNote = "aabcba", magazine = "aaaabbb"
Output: False

'c' is required but not available → cannot construct.

Example 6:

Input: ransomNote = "aabcba", magazine = "aaaabbbccb"
Output: True

All character counts match or exceed what’s needed → can construct.

Key Insight

To construct ransomNote, we need to ensure that each letter in ransomNote exists in magazine in equal or greater quantity.

This means we need to count how many times each letter (from 'a' to 'z') appears in both strings, and verify that for all letters, the magazine count ≥ ransomNote count.

Step 2. Preliminaries: How to Work with Characters in Python (ord() and chr())

Before diving into the full implementation, let’s take a moment to understand two essential Python functions for handling characters: ord() and chr(). Mastering these functions makes it much easier to deal with character data like alphabets.

What is ASCII?

Computers don’t understand letters directly—they process everything as numbers. ASCII code (American Standard Code for Information Interchange) is a universal standard that assigns a unique integer to each character (letters, digits, punctuation, etc.).

Here are a few examples:

• Lowercase 'a' is 97

• Lowercase 'b' is 98

• ...

• Lowercase 'z' is 122

You don’t need to memorize these values. What matters is that the lowercase letters 'a' through 'z' (and uppercase 'A' through 'Z') are assigned consecutive numeric values in ASCII. This makes it easy to calculate character positions and differences.

ord(): Convert Character to Number / chr(): Convert Number to Character

ord(c) takes a character c and returns its corresponding ASCII integer value, while chr(i) takes an integer i and returns the character represented by that ASCII value.

x = ord('a')   # x becomes 97
y = ord('c')   # y becomes 99

print(x + y)   # Outputs 196

z = chr(98)    # z becomes 'b'
print(z)

You can combine them to do character arithmetic. For example, to get the character two steps after 'a':

x = ord('a') + 2  # x = 99
print(chr(x))     # Outputs 'c'

# Or in one line:
print(chr(ord('a') + 2))  # Outputs 'c'

Looping Through the Alphabet with ord() and chr()

Using these functions, we can loop from 'a' to 'z' efficiently. There are 26 lowercase letters, and each letter is ord('a') + i where i ranges from 0 to 25.

for i in range(26):
    x = ord('a') + i  # Get ASCII value
    ch = chr(x)       # Convert back to character
    print(ch)         # Prints 'a' to 'z'

This approach is essential when solving problems that require character frequency counting or alphabet iteration.

Why can't we use range('a', 'f') in Python?

Because range() only works with integers, not characters. Python doesn't inherently know that 'a' is followed by 'b', or whether it should go to 'aa' next. That’s why we use ord() to convert characters to integers before using them in ranges.

• Background knowledge: Sum and Difference of ASCII Codes

Step 3. Iterating Through Each Character and Comparing Counts (Naive Approach, O(Alphabet Size × (N + M)))

Idea and Structure

The most straightforward method is to compare the frequency of each alphabet letter (from 'a' to 'z') in both ransomNote and magazine.

1. Counting a Specific Character: First, let's consider how to count the number of times a specific character (e.g., 'a') appears in ransomNote. Iterate through the string, incrementing a counter each time 'a' is encountered.

# (Example) Assume ransomNote = "banana" and count the number of 'a'
cnt = 0
for c_in_ransomNote in ransomNote:
    if c_in_ransomNote == 'a':
        cnt += 1
print(cnt) # This will print 3 for banana"

1. Counting and Comparing in Both Strings: Apply the same method to both ransomNote and magazine, then compare the counts. If ransomNote requires more of a character than magazine provides, return False.

# Count 'a' in ransomNote
ransom_cnt = 0
for c_in_ransomNote in ransomNote:
    if c_in_ransomNote == 'a':
        ransom_cnt += 1

# Count 'a' in magazine
magazine_cnt = 0
for c_in_magazine in magazine:
    if c_in_magazine == 'a':
        magazine_cnt += 1

# If ransomNote needs more 'a's than magazine has
if ransom_cnt > magazine_cnt:
    return False

1. Repeating for All Alphabets: Repeat the above comparison for all letters from 'a' to 'z' using ord() and chr() functions.

for num in range(26):  # num goes from 0 to 25
    x = ord('a') + num
    ch = chr(x)  # current character being checked

    ransom_cnt = 0
    for c_in_ransomNote in ransomNote:
        if c_in_ransomNote == ch:
            ransom_cnt += 1

    magazine_cnt = 0
    for c_in_magazine in magazine:
        if c_in_magazine == ch:
            magazine_cnt += 1

    if ransom_cnt > magazine_cnt:
        return False

1. Encapsulating into a Function: Combine the above logic into a single function.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for num in range(26):
            x = ord('a') + num
            ch = chr(x)

            ransom_cnt = 0
            for c_in_ransomNote in ransomNote:
                if c_in_ransomNote == ch:
                    ransom_cnt += 1

            magazine_cnt = 0
            for c_in_magazine in magazine:
                if c_in_magazine == ch:
                    magazine_cnt += 1

            if ransom_cnt > magazine_cnt:
                return False

        return True

Time and Space Complexity

• Time Complexity: O(26 × (N + M)) = O(N + M), where N and M are the lengths of ransomNote and magazine, respectively.

• Space Complexity: O(1), as only fixed-size variables are used.

This method is easy to understand but inefficient for longer strings due to repeated traversals.

• Background knowledge: Count of Odd Numbers 2 , Is there a multiple of c between a and b?

Step 4. Optimisation Using a Counting Array (O(N + M))

Idea: Avoid Redundant Computation

While Step 3 works fine, we can optimise further. In Step 3, we calculate the frequency of each character separately for both ransomNote and magazine—for every character from 'a' to 'z'. That means we're re-scanning both strings 26 times.

But what if we could scan each string only once and still collect all the necessary counts? That's where the Counting Array (Frequency Array) comes in.

Logic Breakdown: How to Use a Counting Array in This Problem

1. Preparing the Counting Arrays We need to track the number of times each lowercase letter ('a' to 'z') appears in both ransomNote and magazine. To do this, we create two integer arrays of size 26, one for each string, and initialise them to 0.

ransom_cnt = [0] * 26
magazine_cnt = [0] * 26

In this setup:

• ransom_cnt[0] corresponds to the letter 'a',

• ransom_cnt[1] corresponds to 'b',

• and so on, up to ransom_cnt[25] which corresponds to 'z'. The same applies for magazine_cnt.

1. Count characters in ransomNote (Example: "aabcba")

Let’s take ransomNote = "aabcba" as an example and walk through how we populate the ransom_cnt array:

• Initial state: ransom_cnt = [0, 0, 0, ..., 0] (all values are 0)

• Read the first character 'a': This corresponds to index 0, so we increment ransom_cnt[0] → ransom_cnt = [1, 0, 0, ..., 0]

• Read the second character 'a': Again, index 0 → ransom_cnt = [2, 0, 0, ..., 0]

• Read the third character 'b': Index 1 → ransom_cnt = [2, 1, 0, ..., 0]

Repeat this for all characters in ransomNote.

Final result:

ransom_cnt = [3, 2, 1, 0, ..., 0] → meaning 3 a’s, 2 b’s, 1 c, and the rest are 0.

1. Mapping Characters to Array Indices For each character c in the string, we need to figure out which index in the array to increment.

You could do this with a long chain of if-elif statements:

ransom_cnt = [0] * 26
for c_in_ransomNote in ransomNote:
    if c_in_ransomNote == 'a':
        ransom_cnt[0] += 1
    elif c_in_ransomNote == 'b':
        ransom_cnt[1] += 1
# ... up to 'z'

But that’s verbose and inefficient. A cleaner way is to use the ord() function, as we learned in Step 2.

This allows us to compute the correct array index with a single line:

idx = ord(c) - ord('a')

Explanation:

• 'a' → ASCII 97 → 97 - 97 = 0

• 'b' → ASCII 98 → 98 - 97 = 1

• …

• 'z' → ASCII 122 → 122 - 97 = 25

This index maps directly to our 0–25 counting array.

Now the frequency-counting code becomes very concise:

ransomNote = "aabcba"
ransom_cnt = [0] * 26

for c_in_ransomNote in ransomNote:
    idx = ord(c_in_ransomNote) - ord('a')
    ransom_cnt[idx] += 1

# Result: ransom_cnt = [3, 2, 1, 0, ..., 0]

1. Repeat the process for magazine

We follow the exact same steps to fill the magazine_cnt array:

# Count frequencies for ransomNote
ransom_cnt = [0] * 26
for c_in_ransomNote in ransomNote:
    idx = ord(c_in_ransomNote) - ord('a')
    ransom_cnt[idx] += 1

# Count frequencies for magazine
magazine_cnt = [0] * 26
for c_in_magazine in magazine:
    idx = ord(c_in_magazine) - ord('a')
    magazine_cnt[idx] += 1

1. Compare the Two Counting Arrays

At this point, both ransom_cnt and magazine_cnt contain the number of times each letter from 'a' to 'z' appears in the respective strings.

We now compare these two arrays. For every index from 0 to 25 (i.e., for each alphabet letter), we check whether ransomNote requires more instances of a character than magazine can provide.

If we find any index where ransom_cnt[i] > magazine_cnt[i], we return False.

1. Final Implementation

Here’s how everything comes together in the final canConstruct function:

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # Initialise frequency arrays for a–z
        ransom_cnt = [0] * 26
        magazine_cnt = [0] * 26

        # 1. Count letters in ransomNote
        for c_in_ransomNote in ransomNote:
            idx = ord(c_in_ransomNote) - ord('a')
            ransom_cnt[idx] += 1

        # 2. Count letters in magazine
        for c_in_magazine in magazine:
            idx = ord(c_in_magazine) - ord('a')
            magazine_cnt[idx] += 1

        # 3. Compare frequencies
        for i in range(26):  # from 'a' to 'z'
            if ransom_cnt[i] > magazine_cnt[i]:
                return False  # not enough characters in magazine

        return True  # all characters are sufficiently available

This function efficiently determines whether ransomNote can be constructed using the letters from magazine.

Time and Space Complexity Analysis

• Time complexity: O(N + M)

  • Scanning ransomNote: O(N)

  • Scanning magazine: O(M)

  • Comparing arrays: O(26), treated as O(1)

• Space complexity: O(1)

  • Uses two fixed-size arrays of length 26.

Because this method avoids repeated scanning, it's up to 26 times faster than the naive approach from Step 3. In coding interviews, being able to articulate these optimisation points clearly is a big plus.

Practical example: Counting Occurrences of Numbers 1–9

Frequently Asked Questions

Q. Why is the first approach (Step 3) considered inefficient?

→ In Step 3, we loop over every letter from 'a' to 'z', and for each one, we scan both the ransomNote and magazine strings from start to end. If the strings are long, this repeated scanning becomes highly inefficient due to the increase in total operations.

Q. When is a counting array useful?

→ A counting array is highly effective when the number of possible input types is limited and predictable—for example, lowercase letters ('a' to 'z') or digits (0 to 9). It efficiently computes frequencies like a hashmap, but with simpler logic and faster access when keys are integers in a fixed range.

Q. Can I just use Python’s collections.Counter?

→ Absolutely. In real-world coding or interviews, using collections.Counter is a Pythonic and convenient solution. It works like a built-in hashmap and allows easy comparison of frequencies. That said, during interviews, it's good practice to first explain the logic using a counting array, then mention that Counter can be used as a more concise alternative.

Here’s how that would look:

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        ransom_counts_map = Counter(ransomNote)
        magazine_counts_map = Counter(magazine)

        for char_key, count_needed in ransom_counts_map.items():
            if magazine_counts_map[char_key] < count_needed:
                return False
        return True

How to Prepare for Interviews with the Ransom Note Problem

The Ransom Note problem is an excellent example of frequency comparison in strings and an opportunity to show how you optimize from a basic approach to a more efficient one. It demonstrates your ability to analyse constraints and choose the right data structure accordingly.

You’ll Strengthen the following skills:

• Accurately identifying the core requirement: comparing letter frequencies

• Starting with a naive solution, then recognising its inefficiencies

• Applying a counting array or hashmap to reduce time complexity

• Using ord() and chr() for mapping letters to array indices (Step 2)

How to Review After Solving This Problem

1. Be able to clearly explain the time complexity difference Explain why the counting array version is theoretically up to 26x faster than the naive version.

2. Practice implementing the counting array from scratch Make sure you’re comfortable with the trick: ord(char) - ord('a').

3. Try solving similar frequency-based problems These are excellent follow-ups:

   • 242. Valid Anagram

   • 387. First Unique Character in a String

   • 49. Group Anagrams

   • Dice Game (Codetree)