Letter is Constructible from Magazine

The problem in this post is concerned with answering the question of whether a given letter can be reconstructed with a given magazine. The letter is reconstructible when all the characters in the letter can be accounted for in the magazine, meaning the number of times each character appear in the letter is less than the number of times it appears in the magazine.

Approach

The brute force approach is to get the character frequency in the letter and making sure the same number or more characters exist in the magazine. This requires that we loop through the letter once and another pass over the magazine to balance out the letter's character frequency. A slightly optimized approach is to take away from the letter's character frequency as we iterate through the magazine. We can short circuit the second loop early when we reach a point where the letter's character inventory is empty, indicating that all the characters in the letter has been accounted for.

Implementation

public static boolean isConstructible(String letter, String magazine) {
    // Assume strings are not empty
    // Assume letter.length() >= magazine.length()

    Map<Character, Long> letterFrequency = letter.chars()
        .mapToObj(c -> (char) c)
        .collect(Collectors.groupingBy(
            Function.identify(), Collectors.counting()));

    for (int i = 0; i < magazine.length(); i++) {
        Character c = magazine.charAt(i);
        if (!letterFrequency.contains(c))
            continue;

        letterFrequency.put(c, letterFrequency.get(c) - 1);
        if (letterFrequency.remove(c, 0L)) {
            letterFrequency.remove(c);
            if (letterFrequency.isEmpty())
                break;
        }
    }

    return letterFrequency.isEmpty();
}

This article is my 32nd oldest. It is 233 words long, and it’s got 0 comments for now.