Strings, your first class type

Why this matters

Names, messages, file paths, search queries and input lines are all text. In a coding interview, a large share of the questions are about text: is this word a palindrome, are these two words anagrams, which letter appears most often, how do you reverse a sentence. The C++ type for text is std::string, and it appears in almost every program you will write. Three mistakes about strings cause most of the bugs beginners meet. One is mixing a string with a plain "text" literal in a way that quietly does pointer arithmetic. Another is subtracting from size(), which is an unsigned number. The third is asking for an index that does not exist. This lesson covers all three, and then uses strings to practise the two patterns you will need for the rest of the course: two pointers and counting.

The idea: a string is a row of lockers

A std::string is a sequence of characters. Unlike int or char, it is a class type: a value that comes with built-in actions called member functions. You call one with a dot after the value, as in word.size(). You will learn to write your own class types in a later module. For now, treat a std::string as a value that knows how to answer questions about itself. You need #include <string> to use it.

Think of a string as a row of numbered lockers. Each locker holds one character. The lockers are numbered from 0, not from 1. The number on a locker is called its index. The first character is at index 0, and the last character is at index size() - 1.

std::string word = "Forge";

The string has five characters, so word.size() is 5, but the last index is 4. Off-by-one errors, where a loop or an index is one too far, are the most common bug in text algorithms. Keep the table in mind whenever you write an index.

Useful member functions

The std::string class has dozens of member functions. You need about ten of them in the first month. The program below uses most of them on one word. Read the code and predict each line before you run it.

5
F
or
3
1
18446744073709551615
Fe
F0rge
F0rge! 6
0rge!

Here is what each one does, with the exact rule that interviewers ask about.

• size() counts the characters. length() is the same thing. It is a function, so the brackets are required. Its result type is std::size_t, an unsigned number, which matters in the traps below.
• word[i] returns the character at index i. It prints F and not "F", because the result is a char. It does not check the index.
• at(i) does the same as [i] but checks the index and throws an exception when it is out of range.
• substr(start, count) returns count characters from index start. The second argument is a length, not an end index. That is different from Java, where the second argument is an end index. If count is too large, the result just stops at the end of the string.
• find(x) returns the first index where the character or text appears. When it does not appear, it returns the special value std::string::npos, which is the largest possible size_t. That is the huge number 18446744073709551615 in the output. You must compare with npos before using the result as an index.
• front() and back() return the first and last characters.
• += adds text to the end in place. erase(start, count) removes characters in place.
• empty() is true only for the empty string "".

Unlike strings in Java or Python, a std::string can be changed in place: the line word[1] = '0'; replaced the o. That is the biggest difference from the other tracks, and it is covered next.

Strings are values that you can change

A std::string owns its characters. When you write std::string b = a;, the computer makes a full copy, so a and b are two independent strings. Changing one does not change the other.

Forge forge
Age: 20
rge
ab12
43
ababababab 10

The first line shows the copy: b changed and a did not. The copy costs time proportional to the length, which is why functions that only read a string take it as const std::string&, a reference that avoids the copy. You saw that form in the character arithmetic lesson.

Joining text with +

The + sign joins a std::string with another std::string, with a char, or with a plain text literal. It does not join a string with a number. For that you convert the number first with std::to_string. The reverse direction is std::stoi, which reads an int out of text.

There is one trap here that Java and Python do not have. A literal such as "Forge" is not a std::string. It is an array of characters, and in an expression it turns into a pointer to its first character. Adding a number to a pointer moves it along the array, so "Forge" + 2 is the text that starts at index 2. The output above shows rge. The compiler accepts it without a word, and the result is almost never what you meant. The compiler does reject the case of two literals:

l.cpp:2:33: error: invalid operands of types 'const char [2]' and 'const char [2]' to binary 'operator+'

for "a" + "b". Make sure at least one side of every + is a std::string, as in std::string("a") + "b".

Joining in a loop is cheap in C++, because text += "ab" extends the string in place. Strings reserve extra room as they grow, so building n characters one piece at a time takes time proportional to n overall. The expression text = text + "ab" is the slow form, because text + "ab" builds a whole new string and then copies it back. Prefer +=.

The interview version of this rule is short: "+= appends in place and is amortised O(1) per piece; s = s + piece copies the whole string each time, so a loop of them is quadratic." Say it that way, and give the reason.

Comparing strings: == works

In C++, the == operator on two std::string values compares the characters. That is different from Java, where == compares addresses. You can also use <, >, <= and >=, which compare in dictionary order. The compare member function returns a negative number, zero or a positive number.

1
0
1
-1
0
2
1

The first line is 1 because the two strings hold the same characters, even though b was built in two steps. The second line is 0 because c_str() returns the address of the characters, and a and b store theirs in different places. That is the comparison Java's == makes, and in C++ you have to ask for it on purpose. The < line is 1 because "java" comes before "kava".

The compare result is for sorting. The exact number is not a promise, but the sign is. In the program, "java" against "javb" gives a negative number, and "cat" against "car" gives a positive one, because the first difference is t against r, and the code for t is larger. Your code should test the sign, not the number.

The one trap is a comparison between a string and a character array when both sides are literals: "abc" == "abc" compares two pointers, not text. As long as one side is a std::string, the comparison is by characters.

Indexes and the exception you will see

The [] operator does not check the index. Asking for word[5] on a five-letter word reads past the end. For std::string there is one exception to that: word[word.size()] is allowed, and gives the terminating '\0' character that every string keeps. Anything further is undefined behaviour, which means the program may print garbage, crash or seem to work.

The at function checks, and throws an exception that you can catch.

caught: basic_string::at: __n (which is 5) >= this->size() (which is 5)
caught: basic_string::substr: __pos (which is 9) > this->size() (which is 5)
rge

The message says the index was 5, the size was 5, and the valid indexes are 0 to 4. The substr(9) call fails because the start is past the end. The last call, substr(2, 9), does not fail, because only the start position is checked, and a count that is too large is trimmed to the end of the string.

You avoid these errors by writing loop conditions that stop before the size, such as i < word.size(), and by writing word.size() - 1 whenever you need the last index. The next section shows the one case where that subtraction misleads you.

The unsigned size trap

size() returns an unsigned number. An unsigned number cannot be negative, so when it would go below zero it wraps around to the largest value instead. For an empty string, s.size() - 1 is not -1. It is 18446744073709551615.

loop 0
loop 1
loop 2
loop 3
done

The string is empty, so a correct loop should not run at all. It runs, because s.size() - 1 is a huge number. Only the break stopped it. The compiler warns about the comparison of int and an unsigned number when you build with -Wall -Wextra, and that warning is worth reading. The safe habits are to compare as i + 1 < s.size(), or to store the size in an int first with static_cast<int>(s.size()) when you need to subtract from it. The palindrome program below does the second.

Two pointers: the palindrome check

A palindrome is a word that reads the same backwards, such as racecar. The most direct check is to compare the first character with the last, the second with the second-to-last, and so on, until the two positions meet in the middle. Each position is an index, and the two indexes move towards each other. Programmers call this the two-pointers pattern.

Step through the algorithm below. The two markers are the pointers. Watch the comparison at each step, and what happens when the markers cross.

The rule in code is simple. Start left at 0 and right at the last index. While left is less than right, compare the two characters. If they differ, the word is not a palindrome, and you stop. If they match, move left one step right and right one step left. If the loop ends without a difference, the word is a palindrome.

In the Input box, type racecar and run the program. You should see:

racecar is a palindrome

Type forge instead, and the output is forge is not a palindrome. The if and while statements are the subject of later modules. Read while (left < right) as "repeat while the markers have not met", and read if as "when this is true, do this".

The static_cast<int> on the size matters. With an empty line, word.size() - 1 would wrap around to a huge unsigned number, and right would be wrong. After the cast, right is -1, so left < right is false at the start and the answer is "palindrome", which is correct, because the empty string reads the same both ways. A single letter also gives left equal to right at the start, and the loop does not run, so it is a palindrome too. Interviewers ask about these, and a good answer names them before they do.

The cost is one pass over the string, so the time is proportional to the length n. The extra space is two integers, which does not grow with the input. Write both facts when you explain the solution: time O(n), space O(1).

Counting characters

Many string questions ask how often each character appears. Anagram checks, the most frequent letter and duplicate detection all start with counting. The tool for counting is an array of counters, one for each possible letter. A lowercase English letter maps to a number from 0 to 25 by subtracting 'a'. That works because each letter has a code, and the codes of a to z are consecutive.

Here is the idea with the word banana. The letter b is code 98, so 'b' - 'a' is 1, and counts[1] is the counter for b. The letter n is code 110, so 'n' - 'a' is 13. The letter a gives 0.

The visualizer shows the same idea with a table that maps keys to counts. A hash table does the mapping for any key, which is useful when the characters are not just lowercase letters. For lowercase letters, a plain array of 26 counters is faster and simpler, and it is what the program below uses.

Type banana into the Input box. The output lists the letters that appear, in alphabetical order:

a: 3
b: 1
n: 2

Trace the first counts. The array starts with 26 zeros, because = {} sets every slot to zero. The first character b makes counts[1] equal to 1. The next character a makes counts[0] equal to 1. The third character n makes counts[13] equal to 1. The fourth is another a, so counts[0] is 2, and so on. The second loop walks the array from 0 to 25 and prints the counters that are not zero. The line char letter = static_cast<char>('a' + k); turns the index back into a letter, which is the reverse of the subtraction.

The loop for (char c : text) is a range-based for loop. Read it as "for each character c in text". The array int counts[26] is a list of 26 values. You will study arrays in depth in a later module. For now, read ++counts[c - 'a'] as "add one to the counter for this letter". If the input held a capital letter or a space, c - 'a' would be negative or too large, and the program would write outside the array, so this program assumes lowercase letters only.

Anagrams: two ways to check

Two words are anagrams if they contain the same letters with the same counts, in any order. listen and silent are anagrams. The simplest correct method sorts the letters of both words and compares the sorted results. If the sorted strings match, the words are anagrams.

Type listen on the first line of the Input box, press Enter, and type silent on the second line. The output is:

anagram

std::sort rearranges the characters of the string in place, and begin() and end() mark the range to sort. Sorting takes time proportional to n times the logarithm of n, which is fast enough for most inputs. The counting method from the previous section takes time proportional to n, and it is the better answer when the interviewer asks you to go faster. Both methods are correct. Say both, state the complexity of each, and then pick the one that matches the constraints. This is how you show that you know the trade-off rather than memorising one answer.

Reversing a string in place

Because a std::string can be changed, you can reverse one directly. Swap the characters from the two ends, and move the two indexes towards each other. This is the two-pointers pattern again. The example below works on a copy, so you can see that the original stays the same.

egroF
Forge

std::swap exchanges two values, so the usual three-step swap with a temp variable is already done for you. The original word is still Forge, because letters is a separate copy. The interview version asks you to reverse "in place", meaning with O(1) extra space. Do it on the string itself, without the copy, and you meet that requirement. The standard library also has std::reverse(s.begin(), s.end()), which is common in practice.

Splitting a line into words

Many inputs are one line of words separated by spaces. C++ has no split function, but there is a short and reliable idiom. You put the line into a std::istringstream, which is a stream that reads from a string instead of the keyboard, and then use >> on it exactly as you would on cin.

Type one two three into the Input box. The output is:

Words: 3
First: one
Last: three

Now type a b with two spaces between the letters. The output says Words: 2, because >> skips any run of spaces before a word, so no empty piece appears. That is different from Java, whose split(" ") gives an empty piece for a double space, and it is usually what you want. If you need to cut at a character other than a space, such as a comma, use std::getline(in, part, ',') in the loop instead, and then an empty piece between two commas does appear.

The first unique letter

A common interview question asks for the first character that appears exactly once. The counting method from earlier gives the answer in two passes. The first pass fills the counters. The second pass walks the string from the left and returns the first letter whose counter is 1. The program below is a complete example. Trace it with the sample word swiss.

For the input swiss, the counters are s = 3, w = 1 and i = 1. Walking from the left, s has count 3, so it is skipped. The next letter w has count 1, so the program prints:

First unique letter: w at index 1

and return 0 ends main early. For the input aabb, every letter has count 2, the second loop finishes without a match, and the program prints No unique letter.

The two loops each take time proportional to n, so the total is O(n). The counters take 26 slots, which is a fixed amount of space. A hash-table answer also works in O(n) and handles any characters, but the array is the simpler choice when you know the alphabet. Mention that the choice of 26 depends on the lowercase assumption, and ask the interviewer whether uppercase or digits can appear.

Characters are numbers, and a string is bytes

A char in C++ is a one-byte number, usually 0 to 127 for ordinary text. Each value stands for one character in the ASCII table, so 'A' is 65 and 'a' is 97. This is why c - 'a' works and why static_cast<char>('a' + 1) gives b. The arithmetic happens on the numbers behind the characters.

A std::string stores bytes, not letters. Text in other scripts, such as Devanagari, and most emoji take two to four bytes for one visible character when stored as UTF-8. Then size() counts bytes, not what a reader sees as characters. Interview questions on strings usually assume plain ASCII letters, and it is good practice to say so.

Interview questions about strings

These questions come up often. Practise each answer out loud, and include the complexity.

Why is s == t fine in C++ but wrong in Java? In C++, == on two std::string values is defined to compare characters. In Java, == on two objects compares references. The C++ trap is the case where both sides are literals or char* pointers, because then == compares addresses.

What is the time complexity of s.size()? O(1), because a string stores its length. Checking the size is cheap, so you can use it in a loop condition without worrying about the cost.

What is the time complexity of s.substr(a, n)? O(n), because the new string copies the characters it returns. A solution that calls substr inside a loop over all positions can become O(n squared) without you noticing. A std::string_view avoids the copy and is worth naming in an interview.

How do you reverse a string in C++? Swap from both ends with two indexes, or call std::reverse(s.begin(), s.end()). Both are O(n) time and O(1) extra space.

Is a std::string mutable, and why does that matter? Yes. You can change it in place, which makes += and index assignment cheap. The cost is that passing a string by value copies it, so a function that only reads takes const std::string&.

How would you check whether a string has all unique characters? Use a counter array for lowercase letters in O(n), or sort the characters in O(n log n), or use a set in O(n) on average. Ask about the alphabet first, because that decides which method you choose.

How do you check whether "erbottle" is a rotation of "waterbottle"? Check that the lengths match first, then check that the second string appears inside the first string joined with itself, using find. The text waterbottlewaterbottle contains erbottle, so the answer is yes. The length check matters, because without it a short word can appear inside a longer string and give a false yes.

Debugging walkthrough: a palindrome check that fails

A teammate writes this palindrome check and reports that aa is not a palindrome.

int left = 0;
int right = word.size();
while (left < right) {
    if (word[left] != word[right]) {
        return false;
    }
    ++left;
    --right;
}
return true;

Follow the steps. First, reproduce the bug on the smallest input. aa has size 2. Second, check the starting values. right is set to word.size(), which is 2, not word.size() - 1, which is 1. Third, trace the first comparison: word[0] is a, and word[2] is the terminating '\0', which is a legal read for a std::string but is not a. The function returns false. Run on aa, the program prints 0, which means false.

Notice what did not happen. Java would have thrown an exception here, and the teammate would have seen the line. C++ read the hidden '\0' without a word, so the bug shows up as a wrong answer with no message. That is why you test the smallest and largest valid inputs. Fourth, find the cause: right starts one past the last index. Fifth, fix it with static_cast<int>(word.size()) - 1. Sixth, test the edge cases again: an empty string, a single letter and an even-length word.

The lesson of this walkthrough is that off-by-one errors are found by testing the smallest and largest valid inputs, not by reading the code once. Check the first index, the last index and one step past each.

What happens in memory

A variable of type std::string is a small object that holds the size, a capacity (how much room it has before it must grow) and a pointer to the characters. For short texts, about 15 characters on g++, the characters live inside the object itself, so no extra memory is needed. For longer texts, they live in a separate block that the string allocates and frees by itself.

This explains the == result from earlier. a and b own different blocks, so a.c_str() == b.c_str() is false. a == b opens both blocks and compares the contents, and they match. It also explains std::string b = a;: the computer allocates a new block and copies the characters, so after that the two strings are unrelated.

The memory view also explains the cost of text = text + "ab". Each pass creates a temporary string with a new block, copies the old contents into it, and then copies or moves it back. A string that grows with += keeps its block and, when the block is full, allocates one about twice as large, so the copying happens only a few times in total. That doubling is why += is cheap on average.

Common mistakes

These are the mistakes beginners make with strings. Each one comes with the message you will see or the wrong answer you will get.

• Adding a number to a literal. "Forge" + 2 compiles and gives rge. Use std::to_string(2) and make one side a std::string.
• Adding two literals. "a" + "b" is a compile error. Write std::string("a") + "b".
• Subtracting from size(). On an empty string s.size() - 1 is a huge number. Cast to int first or rewrite the condition.
• Index past the end. word[5] on a five-letter word is undefined behaviour, and at(5) throws std::out_of_range. The valid indexes are 0 to size() - 1.
• Forgetting that find can return npos. Using the result as an index without checking gives a wrong answer or an exception later, in a place that does not look related.
• Mixing up substr arguments. The second argument is a length, not an end index.
• Reading a line after reading a number. If you call cin >> n and then getline, the second call sees the leftover Enter key. The cin lesson covers this trap in detail.
• Mixing up char and std::string. 'a' is a char and "a" is a character array. 'a' + 1 is the number 98, while std::string("a") + "1" is the text a1.
• Using == on pointers. Comparing two const char* values compares addresses, not text. Keep the data in std::string.

Practice

Attempt each exercise on your own first. Use the Input box for the ones that read text.

1. Read a word, then print its last character. Use size() and back() or []. Test it on a single-letter word.
2. Predict the output of std::string("a") + std::to_string(1) + std::to_string(2) and 1 + 2. Then run both.
3. From "Programming", print "gram" using substr. Hint: the second argument is a length.
4. Read a sentence with getline and print how many spaces it contains. Use a range-based loop and compare with ' '.
5. Read a word and print it reversed, without using std::reverse. Use the swap from the reversal example.
6. Read two words and print same if they are equal ignoring case, or different otherwise. Convert each character with std::tolower from <cctype>.
7. Read a word and print yes if it contains the letter e, using find and checking against npos.
8. Build the string 1 2 3 4 5 (numbers separated by single spaces) with += and std::to_string, then print it.
9. Read a word and print the number of vowels in it, counting a, e, i, o and u in lowercase.
10. Explain, in two sentences, why text = text + "x"; inside a loop of 100000 passes is slower than text += "x";.
11. Read a word and print 1 if the first and last characters are the same letter. Make sure a one-letter word is handled.
12. Write a program that reads one line and prints the most frequent lowercase letter. If there is a tie, print the letter that comes first alphabetically.

What you now know

• A std::string is a class type with member functions such as size(), [], at, substr, find and +=. Indexes start at 0 and the last index is size() - 1.
• Strings are mutable values. Copying one makes an independent copy, and += appends in place.
• + joins text from left to right, but needs at least one std::string operand. A literal plus a number does pointer arithmetic.
• == and < compare string contents. compare gives the sign for ordering.
• size() is unsigned, so s.size() - 1 on an empty string wraps to a huge number. Cast to int before subtracting.
• The two-pointers pattern checks palindromes and reverses text in time O(n) and extra space O(1).
• Counting with an array of 26 counters, using c - 'a' as the index, solves anagram and frequency questions.
• Use at when you want a checked index, and test the smallest and largest inputs, because [] past the end can fail silently.