CodingGyan

Ransom Note

easy Strings

Problem

Two words are given: a note and a magazine. Each letter of the magazine can be used only once. Print true if the note can be built from the letters of the magazine, otherwise false.

Constraints

  • 1 <= length <= 10^5
  • lowercase letters

Examples

Input

aa aab

Output

true

Input

aa ab

Output

false

Solutions

Best approachTime O(n + m)Space O(1)

A count of the magazine letters is like a bag. Every note letter takes one letter out of the bag. If the bag is empty for a letter, the answer is false. O(n + m).

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Can the note be built?
 * Input   : Note and magazine.
 * Output  : true or false.
 * Approach: Letter counts
 * Time    : O(n + m)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static boolean solve(String a, String b) {
        // Step 1: Count how many times each letter is in the magazine.
        int[] available = new int[128];
        for (int i = 0; i < b.length(); i++) {
            available[b.charAt(i)]++;
        }
        // Step 2: Every letter of the note uses one letter from the count. If a count is 0, the magazine has too few.
        for (int i = 0; i < a.length(); i++) {
            if (--available[a.charAt(i)] < 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}
Hints (2)
  1. What is the bag?
  2. When do we stop with false?

Try these next