Module assignment: Text tools in C++

Why this assignment exists

You have now met the main tools for text in C++. You can work with char arrays and the null terminator, use std::string for building, slicing and searching, check palindromes and anagrams with two pointers and counters, and solve the common interview problems with scans, windows and stacks. Knowing each tool is one thing. Choosing the right one for a request, wiring several together and making the result reliable is the job you will do at work and in interviews.

This assignment asks you to build one program that answers five kinds of text question. Each question uses a pattern from this module. The program reads its commands from the keyboard, so you test it the same way you have been testing the lesson programs: type input into the Input box and compare the output with what the spec says.

Work through the assignment in order. Read the whole brief first, then write the five functions one at a time, testing each before you start the next. The hints are hidden below the brief. Try the problem yourself first, and open a hint only when you are stuck for more than ten minutes. The reference solution is at the end. Open it only after you have a working version, so you can compare your answers and your reasoning with it.

The brief

Your team runs a small tool called textkit. Support staff type short commands into it, and it answers each one. Each command asks a question about a piece of text. The answers feed into a report, so they must be exact.

The program reads a number first. That number says how many commands follow. Then it reads that many lines, one command per line. The program prints one answer line for each command, in the same order.

Every command line has a command word, then a single space, then an argument. The argument is the text the question is about. Some commands take two words as their argument. The table below lists the five commands.

Any command word that is not in the table gets this answer: ERROR unknown command.

Exact rules for each command

vowels. Count the characters that are one of a, e, i, o or u, in either case. Every other character is ignored, including spaces, digits and punctuation. The answer is one whole number.

palindrome. Ignore every character that is not a letter or a digit, and ignore case. Decide whether the remaining characters read the same forwards and backwards. Answer YES if they do, and NO if they do not. A text with no letters or digits left after cleaning counts as a palindrome, so the answer is YES.

anagram. The argument holds two words separated by one space. Both words contain only letters. Ignore case. Answer YES if the two words have the same letters with the same counts, and NO otherwise. If the argument does not contain a second word, answer ERROR needs two words.

compress. Write each run of equal letters as the letter followed by the number of letters in the run. Leave out the number when the run is exactly one letter. For example, aaabccdddd becomes a3bc2d4. If the argument is empty, print an empty line.

unique. Find the first letter that appears exactly once in the word. Answer with its index, counting from 0. If no letter appears exactly once, answer -1. If the argument is empty, answer -1.

Example runs

The first example uses all five commands and one unknown command. Check your program against it before you read further.

Input:

6
vowels Programming Is Fun
palindrome A man, a plan, a canal: Panama
anagram listen silent
compress aaabccdddd
unique loveleetcode
shout hello

Output:

5
YES
YES
a3bc2d4
2
ERROR unknown command

Work through the first two answers by hand. Programming Is Fun has five vowels, as the lesson on common interview problems showed. The palindrome command cleans A man, a plan, a canal: Panama down to amanaplanacanalpanama, which reads the same in both directions, so the answer is YES.

The second example checks the two cases that are easy to miss: a palindrome that fails after cleaning, and an anagram that fails because the counts differ.

Input:

4
palindrome race a car
anagram rat car
compress aabcccc
unique aabb

Output:

NO
NO
a2bc4
-1

race a car cleans to raceacar, which is not a palindrome. rat and car have different letters, so the anagram answer is NO. aabcccc has runs aa, b and cccc, so the output is a2bc4. Every letter in aabb appears twice, so no letter is unique, and the answer is -1.

Input rules you can rely on

The first line holds one whole number from 1 to 1000. Every command line after it is well formed in the sense that it starts with a command word, and that word is separated from the argument by one space. An argument may be missing. A command line that is only vowels has an empty argument. You must still answer it, and the answer is the same as for an empty text.

Words in compress, unique and anagram contain only lowercase letters, with no digits or punctuation. The anagram command is the one case where case is not guaranteed, because a student may type Listen silent. Ignore case for that command, as the rules say.

A text argument may be up to 10,000 characters long. Your program must handle that size within a second. A solution that calls strlen inside a loop, or that builds a long string with + in a loop, is slow at this size. The rubric checks this.

Requirements checklist

Copy this list into your own notes and tick each item when your program passes it. The checklist is what a reviewer looks at first.

• The program reads the command count, then reads exactly that many command lines.
• vowels counts both capital and small vowels, and returns 0 for an empty argument.
• palindrome ignores spaces, commas, colons, apostrophes and case, and uses a two-pointer scan rather than building a reversed copy.
• palindrome returns YES for an argument with no letters or digits.
• anagram returns ERROR needs two words when no second word is given.
• anagram ignores case, and returns NO for words of different lengths without counting.
• compress writes a count only when a run has more than one letter, and writes a count of 10 or more correctly.
• unique returns the index of the first single letter, and -1 when none exists.
• Any unknown command word prints ERROR unknown command, and the program keeps going with the next line.
• Each of the five commands is a separate function with a comment that states its time and extra space.
• The program does not call strlen inside a loop condition, and does not build a string with + inside a loop.
• The program gives the expected output on both examples above, character for character.

Grading rubric

Your grade depends on how many commands behave correctly on the full set of test inputs, including the edge cases in this brief. Each level describes what a solution at that level looks like.

60 percent. The program prints the right answer for the two examples. It handles the simple cases of each command, such as an ordinary palindrome and a normal anagram, but it fails at least one of these: an empty argument, a palindrome with punctuation, an anagram with capitals, a run of ten or more letters, or an unknown command. The code works, but some functions are long and repeated, and the complexity is not stated.

80 percent. Every command gives the correct answer on the examples and on all of the edge cases listed in the brief. The unknown command and the missing-argument messages are exact. The five functions are separate and named clearly. The complexity comments are present and correct. The program passes a test with 10,000 characters in each argument within a second. There may be small style problems, such as one repeated block that could be a function.

100 percent. Everything in the 80 percent level, plus: the code is organised so that a reviewer can find each rule in one place; the palindrome and anagram functions are the same ones you would present in an interview, with the choice of method explained in one comment; no function does repeated work inside its loop; and the student has tested the program with at least five extra inputs of their own design, written down with their expected output, covering at least one case that the brief does not show. The hidden test list the course uses will include cases like these.

Step-by-step plan

Build the program in this order. Each step is small, and you test it before you go on.

1. Write countVowels from the lesson on common interview problems. Test it with the sentence in the first example.
2. Write isPalindromeClean using the two-pointer skip loops from the palindrome lesson. Test it with the palindrome in the first example and with race a car.
3. Write isAnagram with 26 counters. Make sure you lower-case each letter before you index the counters, because the command accepts capitals.
4. Write compress from the run-scanning pattern. Test it with aaabccdddd and with a run of 12 z letters.
5. Write firstUnique with count-then-scan. Test it with loveleetcode and aabb.
6. Write the reading part of main. Read the count, consume the rest of that line, then read the command lines one at a time.
7. Split each line at its first space into a command word and an argument. Compare the command word with each of the five names, and call the matching function.
8. Add the unknown-command branch and the missing-argument branch for anagram.
9. Run both examples. The output must match exactly, with no extra spaces and no extra blank lines.
10. Add the complexity comments, then test with long inputs and with the extra cases you chose.

Checkpoints

Each checkpoint program covers part of the plan. Run it before you add the next part. The programs leave out the other commands, so their output is only part of the final answer.

Checkpoint 1: reading the commands

Type this input in the Input box: 3, then vowels Programming Is Fun, then unique, then shout hello.

The output is:

command=[vowels] argument=[Programming Is Fun]
command=[unique] argument=[]
command=[shout] argument=[hello]

Checkpoint 2: vowels and palindromes

Type this input: 4, then vowels Programming Is Fun, then palindrome race a car, then palindrome A man, a plan, a canal: Panama, then shout hello.

The output is:

5
NO
YES
ERROR unknown command

Checkpoint 3: compress and unique

Type this input: 3, then compress aaabccdddd, then unique loveleetcode, then compress.

The output is:

a3bc2d4
2
 

The last line of output is an empty line, because compress with no argument prints an empty line.

Checkpoint 4: anagrams and the missing word

Type this input: 3, then anagram listen silent, then anagram Listen, then anagram Listen silent.

The output is:

YES
ERROR needs two words
YES

This checkpoint lower-cases the words before the counting, so Listen and silent count as anagrams.

Hints

Each hint is hidden. Open one only when you are stuck, and try the step again before you open the next.

Reference solution

Try the assignment first. This solution uses the same patterns as the lessons and follows the rules above. Read it for the design choices, not only for the answers. It is written for clarity, and a faster or shorter version is also correct if it gives the same output.

#include <cctype>
#include <iostream>
#include <string>
using namespace std;
 
// Count the vowels in either case. O(n) time, O(1) extra space.
int countVowels(const string& s) {
    int n = 0;
    for (char c : s) {
        char l = (char)tolower((unsigned char)c);
        if (l == 'a' || l == 'e' || l == 'i' || l == 'o' || l == 'u') n++;
    }
    return n;
}
 
// Palindrome that ignores everything except letters and digits, and ignores case.
// Two pointers, skipping characters that do not count. O(n) time, O(1) extra space.
bool isPalindromeClean(const string& s) {
    int i = 0;
    int j = (int)s.size() - 1;
    while (i < j) {
        while (i < j && !isalnum((unsigned char)s[i])) i++;
        while (i < j && !isalnum((unsigned char)s[j])) j--;
        if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j])) return false;
        i++;
        j--;
    }
    return true;
}
 
// Anagram test with 26 counters. Letters only, case ignored.
// O(n) time, O(1) extra space. Different lengths are rejected first.
bool isAnagram(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    int count[26] = {};
    for (char c : a) count[tolower((unsigned char)c) - 'a']++;
    for (char c : b) count[tolower((unsigned char)c) - 'a']--;
    for (int x : count) {
        if (x != 0) return false;
    }
    return true;
}
 
// Run-length encoding: a letter, then its count when the run is longer than 1.
// O(n) time, and the output is built with += so no quadratic copying happens.
string compress(const string& s) {
    string out;
    int n = (int)s.size();
    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && s[j] == s[i]) j++;
        out += s[i];
        if (j - i > 1) out += to_string(j - i);
        i = j;
    }
    return out;
}
 
// Index of the first letter that appears exactly once, or -1.
// Count first, then scan. O(n) time, O(1) extra space for lowercase letters.
int firstUnique(const string& s) {
    int count[26] = {};
    for (char c : s) count[c - 'a']++;
    for (int i = 0; i < (int)s.size(); i++) {
        if (count[s[i] - 'a'] == 1) return i;
    }
    return -1;
}
 
int main() {
    int q;
    cin >> q;
    string rest;
    getline(cin, rest);
 
    for (int k = 0; k < q; k++) {
        string line;
        getline(cin, line);
        size_t space = line.find(' ');
        string cmd = line.substr(0, space);
        string arg = (space == string::npos) ? "" : line.substr(space + 1);
 
        if (cmd == "vowels") {
            cout << countVowels(arg) << "\n";
        } else if (cmd == "palindrome") {
            cout << (isPalindromeClean(arg) ? "YES" : "NO") << "\n";
        } else if (cmd == "anagram") {
            size_t gap = arg.find(' ');
            if (gap == string::npos) {
                cout << "ERROR needs two words\n";
                continue;
            }
            string first = arg.substr(0, gap);
            string second = arg.substr(gap + 1);
            if (first.empty() || second.empty()) {
                cout << "ERROR needs two words\n";
                continue;
            }
            cout << (isAnagram(first, second) ? "YES" : "NO") << "\n";
        } else if (cmd == "compress") {
            cout << compress(arg) << "\n";
        } else if (cmd == "unique") {
            cout << firstUnique(arg) << "\n";
        } else {
            cout << "ERROR unknown command\n";
        }
    }
    return 0;
}

Why the reference solution is built this way

The five functions are separate, because each rule should be easy to find and test on its own. The main function only reads, splits and dispatches. A reviewer who wants to check the palindrome rule opens one function, not the whole program.

The two-pointer palindrome does not build a cleaned copy of the text. A copy would cost O(n) extra space, and the spec allows 10,000 characters, which makes the copy cheap but unnecessary. The skip loops are the clean approach, and the lesson on palindromes explained why each check of i < j matters.

The anagram function checks the length first. The check costs nothing and avoids counting work for words that cannot match. The counters are indexed after lower-casing, so Listen and silent are treated as equal.

firstUnique counts first and scans second, as the pattern in the common interview problems lesson describes. The function returns -1 for an empty word without a special case, because the scan never runs.

Common problems students hit

Most failed checks come from a small number of causes. Check these first.

The output has an extra blank line at the start. This usually happens when the number line is not fully consumed. Use getline once after cin >> q, as the hint describes.

The palindrome answer is wrong for sentences with commas or spaces. The skip loops are missing, or they do not check i < j. Test the first example.

The anagram answer is NO for Listen silent. The counters were not lower-cased before indexing. Check the rule that ignores case.

The program crashes on a missing argument. The code calls substr with a start past the end of the line, or indexes s[0] of an empty string. Check the empty case before each call, and remember that substr(pos) is allowed when pos equals the size.

The program is slow on long input. The code calls strlen in a loop condition, or it builds a result with s = s + c. Store the length once, and use += or push_back.

compress prints a1 for a single letter. The count is written every time, instead of only when the run is longer than one letter. Fix the if test.

unique returns 0 for aabb. The scan returns the first index whose count is not zero, instead of one whose count is exactly 1. Change the test to == 1.

Submitting your work

Keep your program as one file. Put the complexity comment above each function. Run both examples and copy the outputs into your notes. Then write down your five extra test cases, the input and the expected output, so that you can show them to a reviewer. Include at least one case with a longer argument, one with an empty argument, one with capitals, one with punctuation, and one unknown command.