Andrew and COVID | HackerRank Solution

Andrew and COVID is a short HackerRank problem dressed up in a pandemic story. Strip the story away and the question is this: given a pile of characters, how many complete copies of the word "covid" can you build if each character can be used only once and order does not matter? It is a counting problem, and the idea behind it is one of the most useful patterns in beginner coding: count how often each character appears, then let the scarcest one decide the answer.

You will see the same pattern in problems like "how many times can you form the word balloon" or "can this ransom note be made from this magazine". Once you see it here, those become easy.

Problem

Andrew is given a string that may run across several lines. It contains lowercase letters, digits, special characters and spaces. Each character can be used at most once, and the letters do not need to stay in order. Find how many times the word covid can be formed from the characters.

Input format: a multi-line string made of lowercase letters, digits, special characters and spaces.

Output format: one integer, the number of complete copies of "covid" that can be formed.

Constraints: 1 ≤ length of the string ≤ 100.

Input:
c1o1vd11i1

Output:
1

I read "multi-line" as meaning all lines together form one pool of characters, so letters on different lines can be combined into the same "covid".

Approach

Every copy of "covid" needs exactly one c, one o, one v, one i and one d. Suppose the input has 4 c's, 3 o's, 5 v's, 3 i's and 2 d's. You can build two copies, and then you run out of d's. Extra c's and v's do not help. So the answer is the minimum of the five letter counts.

1. Read all input lines until the input ends.
2. Count every lowercase letter in an array of 26 counters, where index 0 is 'a' and index 25 is 'z'.
3. Look up the counts for c, o, v, i and d.
4. Print the smallest of those five counts.

If any one of the five letters is missing, its count is 0, so the answer is 0. That case matters, and we will come back to it.

Dry run on c1o1vd11i1: the letters are c, o, v, d, i, one of each. The digits are ignored. The counts are c=1, o=1, v=1, i=1, d=1. The minimum is 1, so the answer is 1.

Solution in Java

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // One counter for each letter a..z
        int[] count = new int[26];

        // The input can span many lines, so keep reading until it ends
        while (in.hasNextLine()) {
            String line = in.nextLine();
            for (char ch : line.toCharArray()) {
                if (ch >= 'a' && ch <= 'z') {
                    count[ch - 'a']++;
                }
            }
        }
        in.close();

        // Each "covid" needs one of each of these letters
        String word = "covid";
        int answer = Integer.MAX_VALUE;
        for (char ch : word.toCharArray()) {
            answer = Math.min(answer, count[ch - 'a']);
        }
        System.out.println(answer);
    }
}

A few Java details explained:

• in.hasNextLine() returns true while there is still input left. Looping on it lets you read any number of lines without knowing the count in advance.
• ch - 'a' turns a letter into an index. Characters are stored as numbers, and the letters a to z are consecutive, so 'c' − 'a' is 2.
• Integer.MAX_VALUE is a safe starting point for a minimum. The first real count will always be smaller or equal.

What was wrong with the old solution. The earlier code counted only the c/o/v/i/d letters it actually found, in a HashMap, and took the minimum over the map. If a letter never appeared, it was simply not in the map, so it was never considered. For input cov 11 (no i, no d) the old code printed 1, although no complete "covid" can be formed. For input with none of the five letters, like 1234, it printed 2147483647. I ran the old logic on both inputs to confirm. The array version above always looks at all five letters, so missing letters correctly give 0.

My tests: the sample prints 1; cov 11 prints 0; 1234 prints 0; and a three-line input with covidcovid, then cc oo vv ii d d, then @# prints 4 (two copies from line 1 and two more from line 2, since there are exactly four d's).

Output

1

Complexity

O(L) time, where L is the total input length, since each character is looked at once. Space is O(1) because the counter array always has 26 slots.

Common mistakes

• Only checking letters that appear, as the old code did. A missing letter must count as 0.
• Reading just one line with nextLine(). The input can have several lines and letters on later lines also count.
• Searching for the substring "covid" with indexOf. Order does not matter here, so that approach misses scrambled letters like in the sample.
• Removing characters from a string in a loop each time a "covid" is built. It works for 100 characters, but counting is simpler and has no edge cases.

Next in the Java track: Java Stdin and Stdout II.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice