Ransom Note - C Solution

1. Introduction

In this post, we address a string manipulation challenge known as the "Ransom Note" problem. The essence of this problem is to determine if one string (the ransom note) can be formed from the characters of another string (the magazine), considering that each character from the magazine can only be used once. This problem tests one's understanding of string manipulation and character counting in C programming.

Problem

Given two strings, ransomNote and magazine, return true if ransomNote can be constructed using the letters from magazine, and false otherwise. Each letter in magazine can only be used once in ransomNote.

2. Solution Steps

1. Create an array to count the frequency of each character in magazine.

2. Iterate through ransomNote, decrementing the corresponding frequency for each character.

3. If a character in ransomNote is not found in magazine or is used more times than it appears in magazine, return false.

4. If the loop completes without issues, return true.

3. Code Program

#include <stdio.h>
#include <string.h>

// Function to check if ransomNote can be constructed from magazine
int canConstruct(char* ransomNote, char* magazine) {
    int letters[256] = {0}; // Initialize frequency array

    // Count the frequency of each character in magazine
    for (int i = 0; magazine[i] != '\0'; i++) {
        letters[magazine[i]]++;
    }

    // Check if characters of ransomNote are in magazine
    for (int i = 0; ransomNote[i] != '\0'; i++) {
        if (--letters[ransomNote[i]] < 0) {
            return 0; // Character not available
        }
    }

    return 1; // Ransom note can be constructed
}

// Main function to test the canConstruct function
int main() {
    char ransomNote1[] = "a";
    char magazine1[] = "b";
    printf("Can Construct (Example 1): %s\n", canConstruct(ransomNote1, magazine1) ? "true" : "false");

    char ransomNote2[] = "aa";
    char magazine2[] = "ab";
    printf("Can Construct (Example 2): %s\n", canConstruct(ransomNote2, magazine2) ? "true" : "false");

    char ransomNote3[] = "aa";
    char magazine3[] = "aab";
    printf("Can Construct (Example 3): %s\n", canConstruct(ransomNote3, magazine3) ? "true" : "false");

    return 0;
}

Output:

Can Construct (Example 1): false
Can Construct (Example 2): false
Can Construct (Example 3): true

Explanation:

1. Create an array letters to store the frequency of each character in magazine.

2. Increment the frequency count while iterating through magazine.

3. While iterating through ransomNote, decrement the frequency count and check if a character is unavailable.

4. If a character in ransomNote is used more times than available in magazine, return false.

5. If all characters are available, return true.

6. The main function tests canConstruct with three examples and prints whether the ransom note can be constructed.