Palindromes and anagrams

Why it matters

Palindrome and anagram questions appear in interviews more than almost any other string topic. They are short enough to fit in a 20-minute slot, and they test whether you can pick the right pattern. A palindrome check is about symmetry, so you compare from both ends at once. An anagram check is about content, so you count letters and ignore their order. Learn to recognise which kind of question you are facing, and most of the solution follows.

This lesson starts from the plain definitions, builds each method from first principles, and then adds the real-world rules that make the problems harder: ignoring case, ignoring punctuation, allowing one mistake and grouping many words at once. You will run six programs, read each output and trace the steps by hand.

The idea of a palindrome

A palindrome is a text that reads the same forwards and backwards. The words level, noon and a are palindromes. The word hello is not, because reading it backwards gives olleh.

Imagine two people walking toward each other along a line of letter tiles, one starting at the left end and one at the right end. At each step, they check the tile under their feet. If the two tiles match, they keep walking toward the middle. If the two tiles differ, the text is not a palindrome, and they can stop. If they meet in the middle without finding a difference, every mirror pair matched.

That is the two pointers pattern. A pointer here is just an index into the text, a number that says which box you are looking at. Two indexes start at the two ends and move toward each other. In C++ we call them i and j:

• i starts at 0, the first character.
• j starts at size - 1, the last character.
• While i is still less than j, compare s[i] with s[j].
• If they differ, return false. Otherwise move i right and j left.
• If the loop ends, every pair matched, and the answer is true.

The condition i < j is important. When i equals j, the two pointers point at the same character, which always matches itself, so there is nothing left to compare. For an even-length text, the pointers cross without meeting. For an odd-length text such as level, they meet at the middle letter v, which is fine.

Let us trace it on racecar, which has seven characters with indexes 0 to 6.

The middle e is never compared with anything else, which is correct. The loop checked three pairs, each in constant time, so the whole check takes O(n) time for n characters, and it needs O(1) extra space, because it only stores two numbers.

Two pointers starting at both ends of racecar and moving inward until they meet at the middle letter

The two-pointer interactive view

The next visualiser runs the check on a short text. Press the step control to move one comparison at a time and watch the two indexes close in.

Watch for two things. First, the pointers always move one step per comparison, so the number of steps is about half the length. Second, the first mismatch ends the check immediately. A palindrome that is almost right, such as abcba with one letter changed, stops at the first mismatch and never looks at the rest. That early exit is why the typical case is faster than the worst case.

Worked example 1: Checking one word per line

The first program reads words from the keyboard, one after another, and prints YES or NO for each. It uses while (cin >> word), which reads a word, runs the body and repeats until there are no words left. Type level hello noon a Ab in the Input box and press Run.

The output is:

level: YES
hello: NO
noon: YES
a: YES
Ab: NO

The check is case sensitive. Ab has the letters A and b. The first is A, with code 65, and the last is b, with code 98. They differ, so the answer is NO. The next program fixes that by ignoring case.

Note that (int)s.size() - 1 casts the unsigned size to int before subtracting. For an empty string, the size is 0, so j becomes -1. The condition i < j is then 0 < -1, which is false, and the function returns true. An empty string counts as a palindrome. Many interviewers ask you to state this rule out loud.

Clean palindromes

Real palindrome questions ignore spaces, punctuation and letter case. The sentence A man, a plan, a canal: Panama is a palindrome once you keep only the letters and lower-case them: amanaplanacanalpanama. The two pointers still do the work. The change is that each pointer skips characters that do not count before comparing.

The following program reads whole lines with getline, because a sentence contains spaces. Type these three lines, one per line, in the Input box: A man, a plan, a canal: Panama, then race a car, then No 'x in Nixon'.

The output is:

YES
NO
YES

The first line is the famous sentence, so the result is YES. The second line becomes raceacar, which reads racaecar backwards, so the answer is NO. The third line, No 'x in Nixon', becomes noxinnixon, which is a palindrome, so the answer is YES.

Trace the first line. i starts at A and j starts at the final a of Panama. Both are letters, so neither inner loop moves. They match after lower-casing, so both pointers step inward. The left pointer now lands on a space, and its inner loop skips the space. The right pointer lands on m. The outer loop keeps going this way until the pointers meet. The inner loops are the reason the code stays a single pass. Each pointer moves forward through the text at most once, so the total work is still O(n).

The important detail is the cast to unsigned char before isalnum and tolower. These functions expect values from 0 to 255, or the special value EOF. A plain char can be negative for characters outside ASCII on some systems, and passing a negative value is undefined behaviour. The cast avoids that. The rule from the first lesson applies here again.

Edge cases you must name in an interview

Before you write any palindrome code, ask about these cases and say the answer out loud. Interviewers mark candidates on this list.

• Empty string. Usually a palindrome (true). The loop never runs.
• One character. Always a palindrome (true), because the two pointers start on the same box.
• Even and odd length. Both work. Even-length texts have no middle character, and the loop ends when i and j cross.
• Only punctuation. After cleaning, the text is empty, so the answer is true under the usual rule. Confirm what the problem wants.
• Case. Ask whether Aa counts. Most problems say yes, after case is ignored.
• Unicode. Ask whether the input can contain non-ASCII letters. The <cctype> functions only know the ASCII rules, so you may need a different approach for other alphabets.

Almost a palindrome: one deletion allowed

A harder version asks whether the text becomes a palindrome after removing at most one character. Here is the idea. Run the normal two-pointer check. At the first mismatch, i and j point at two different characters. Either removing the character at i or removing the character at j might fix the problem. Check both possibilities with a plain palindrome test on the rest of the text. If one works, the answer is yes. If neither works, the answer is no.

This matters for correctness. Once you have found the first mismatch, the only deletion that can help is one of those two characters. Deleting any other character leaves the mismatch in place.

Take abbca. The outer pairs are a and a, which match. Then b at index 1 and c at index 3 differ. Removing index 1 leaves abca, which is not a palindrome. Removing index 3 leaves abba, which is a palindrome. So the answer is yes.

The next program uses a helper that checks a range inside the text. It reads one word per line of input.

Type abca abc abbca racecar in the Input box and press Run. The output is:

abca: YES
abc: NO
abbca: YES
racecar: YES

Trace abc. The first pair is a and c, which differ. The program then tests two ranges: bc from index 1 to 2 (which fails because b is not c), and ab from index 0 to 1 (which fails because a is not b). Both fail, so the answer is NO.

The helper isPalindromeRange takes the indexes as parameters so it can check a slice without copying it. Copying would cost O(n) extra space and time, which is avoidable here. The whole method runs in O(n) time because the initial scan does one pass, and each of the two helper calls does at most one more pass.

Anagrams: same letters, any order

Two words are anagrams when they use exactly the same letters, the same number of times, in any order. listen and silent are anagrams. rat and car are not, because one has a t where the other has a c. aab and abb are not, because they have different counts of a and b.

Order does not matter, so the question is really about counts. There are three ways to answer it, and each has a different cost.

Method 1: sort both words. Sorting listen gives eilnst. Sorting silent also gives eilnst. Two words are anagrams exactly when their sorted forms are equal. This is short to write and easy to explain. The cost is the sort, which is O(n log n) for words of length n.

Method 2: 26 counters. If the words use only the letters a to z, you can keep one counter for each letter. Add one for each letter of the first word and subtract one for each letter of the second. If every counter ends at zero, the counts match. This is O(n) time, and the space is a fixed 26 boxes, so it is O(1) extra space. It is the method most interviewers expect for lowercase input.

Method 3: a hash map of counts. A hash map is a table that finds a value from a key quickly. Each key is a character and each value is a count. You add one for each character of the first word and subtract one for each character of the second. The map can hold any characters, including capitals, digits and punctuation. The cost is O(n) time on average, because each insert or lookup takes constant time on average. The space depends on how many distinct characters the words contain.

The next section works through Method 2 by hand, and the section after it shows Method 3.

Worked example 2: Counting with 26 counters

The following program checks pairs of lowercase words. It reads two words per line with cin >> a >> b, and the loop repeats while both reads succeed.

Type these three lines in the Input box: listen silent, then rat car, then aab abb. The output is:

listen silent: YES
rat car: NO
aab abb: NO

Trace listen silent by hand. Both words have six letters, so the length check passes. The first loop adds one for each letter of listen. The counters for e, i, l, n, s and t each become 1, and the others stay at 0. The letters are l, i, s, t, e, n. The second loop subtracts one for each letter of silent. The same six counters go from 1 back to 0, because silent uses exactly the same letters. The final loop finds no nonzero counter, so the function returns true.

Six letter counters after listen (all 1) and after silent (all 0)

Now trace rat car. Both words have three letters, so the length check passes. After the first loop, r, a and t are each +1. The second loop subtracts c, a and r. That makes c -1, brings a and r back to 0, and leaves t at +1. The final loop finds nonzero counters for c and t, so it returns false.

The index is c - 'a', not c. A lowercase a has the code 97, so count[97] would be far outside the 26 boxes. The subtraction moves every letter into the range 0 to 25, which is why the counters have exactly 26 boxes.

Worked example 3: The same check with a hash map

Method 3 is more general. It handles capitals, digits, punctuation and spaces without any special cases. The next program uses unordered_map from <unordered_map>. The key is a char and the value is the count. The map creates an entry the first time you use a new key, with a count that starts at 0.

Type night thing, then Abc cba, then ab-c cb-a in the Input box. The output is:

night thing: YES
Abc cba: NO
ab-c cb-a: YES

The second line fails, even though the two words have the same letters apart from case. The map has separate entries for A and a. The first word adds one to A, so A stays at +1, and the second word subtracts one from a, so a drops to -1. The check finds those nonzero entries and returns false. If your problem says case should be ignored, convert both words to lowercase first, as the clean palindrome program did.

The third line works because - is a normal character. The map counts it like any letter, so the words ab-c and cb-a contain the same characters and the answer is YES.

The loop at the end uses auto& to read each entry without copying it. Each entry has two parts, first (the key) and second (the count). The code only needs the count, so it uses entry.second.

Visualising the hash map

The next visualiser builds the count table for two words one character at a time. Watch how the table grows when a new key appears and how the counts move up and down. Notice that the table does not need a box for every possible character, only for the ones that appear.

The main point is that a hash map keeps only the keys you have seen. For lowercase text, the 26-counter array wastes no space and is faster, because it avoids the work of hashing. For a general character set, the map is the right tool. An interviewer may ask why you chose one over the other, and the answer is the size of the character set and whether case or punctuation matters.

Worked example 4: Grouping anagrams

A common follow-up asks you to group a list of words so that anagrams sit together. The trick is to make a key for each word, a value that every anagram shares. Sorting the letters of a word gives a key that is the same for all its anagrams. Words with the same key go into the same group.

The program below reads a line of words, computes each key and stores the words in a map from key to a list of words. A map keeps its keys in sorted order, so the groups print in alphabetical order by key. Type eat tea tan ate nat bat in the Input box.

The output is:

abt: bat
aet: eat tea ate
ant: tan nat

Trace the keys. eat, tea and ate each sort to aet. tan and nat each sort to ant. bat sorts to abt. The map stores these three keys in alphabetical order: abt, then aet, then ant. The words in each group keep the order they appeared in the input, because push_back adds to the end of each list. So tan comes before nat in the ant group, and eat, tea, ate appear in that order in the aet group.

The loop for (const auto& [key, members] : groups) is a structured binding, a C++17 feature. It unpacks each map entry into two names, key and members, so you do not write entry.first and entry.second. The const and the reference avoid copying the lists.

The cost is O(n times k log k) for n words of length at most k, because each word is sorted once, and the map does O(log g) work for each of the g groups. An alternative is to use the 26-counter signature as the key, which gives O(n k) overall. Either is a good answer in an interview if you state the trade-off.

What happens inside

Consider the two-pointer check on a 1,000-character palindrome. The loop runs about 500 times. Each iteration does two array reads, one comparison and two index updates. There are no allocations, because the function only stores two numbers. The cost is linear, and the memory use stays the same whether the text has 10 or 10,000 characters.

Consider the 26-counter anagram check. The vector count is allocated once and holds 26 integers, about 104 bytes. Each letter costs one array update. The length check at the start avoids the counting work when the words differ in size, which is an easy speed gain.

Consider the hash map. When you write counts[c]++, the map computes a hash, a number derived from the key, and uses it to find a bucket, a slot in an internal array of lists. If the key is not present, the map creates an entry with a count of zero first. Average lookups are constant time, but a bad hash function or many collisions (two keys landing in the same bucket) makes them slower. For a short list of characters this never matters.

The grouping program stores each word in a list inside the map. The map itself is a balanced tree, which keeps keys sorted and gives logarithmic time for each insert and lookup. The unordered_map in the earlier example uses hashing instead, which gives average constant time but no order. Choose by need: use map when you must print in order, and unordered_map when you only need fast lookup.

Complexity summary

The table states the cost of each method for a single pair of words, unless the row says otherwise. For grouping, n is the number of words and k is the longest word.

Choosing a method

Interviewers often ask which method you would use, and the answer depends on the input. For lowercase words, the 26-counter method is the usual choice: it is linear, uses a fixed amount of memory, and the code is short. For any characters, a hash map of counts is the general tool. It costs a little more time per character, because each lookup computes a hash of the key. Sorting is the easiest method to explain and to get right. It is fast enough for short words, but it takes O(n log n) time.

The grouping problem changes the choice. Each word needs a key, and the sorted word is a clear key that is easy to read in a debugger. A counter signature also works as a key, but you must turn 26 numbers into one value that a map can store, such as a string of counts. Use the sorted key unless the words are very long and there are very many of them.

Say which assumption you rely on. If the problem says lowercase only, state it, because the 26-counter method depends on it. If you are unsure, sorting is correct for any characters, and you can offer the counter method as an improvement.

Common mistakes

1. Skipping the i < j test in the skip loops. If an inner loop moves i past j, the next comparison reads a box that is outside the range you meant. The inner loops in the clean palindrome must check i < j every time they step.

2. Using count[c] instead of count[c - 'a']. If you forget the subtraction, the index for a is 97 and the vector has 26 boxes. The vector does not check the index, so the write goes past its end. Change count[c] to count.at(c) while you test, and the program stops with this message:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 97) >= this->size() (which is 26)

The message tells you the index used (97) and the size (26). That pair is the clue: 97 is the code for a, which means the subtraction was missing.

3. Comparing with == on the wrong types. If you compare two char arrays with ==, you compare addresses, as the first lesson explained. Use std::string and ==, or strcmp for arrays.

4. Counting case-sensitive letters when the problem ignores case. The map example shows the result. Lower-case both words before counting.

5. Forgetting to handle different lengths. The length check at the top of the 26-counter program is an early exit. Without it, the counters would still catch a longer word, but only after the program had counted every letter. Check the length first and state the rule.

6. Mixing up where the pointers start. The pointers start at the two outer ends and move toward the middle. If j starts at 0 as well, i < j is false from the first step, and every word is reported as a palindrome.

Debugging walkthrough: the function that rejects everything

A teammate wrote this palindrome check. Every word is reported as not a palindrome, including a and aa. They ask you to find the bug.

#include <iostream>
#include <string>
using namespace std;
 
bool isPalindrome(const string& s) {
    int i = 0;
    int j = (int)s.size();
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}
 
int main() {
    string word;
    while (cin >> word) {
        cout << word << ": " << (isPalindrome(word) ? "YES" : "NO") << endl;
    }
    return 0;
}

Start with the smallest failing case, a. The size is 1, so j is set to 1, not 0. The loop runs while i < j, so i is 0 and j is 1, and the loop runs. The check compares s[0], which is a, with s[1]. The string has no box at index 1 for a letter, so s[1] returns the terminator '\0', which is a legal value for std::string in C++11 and later but never a letter. So a differs from the terminator and the function returns false. The output is a: NO.

The fix is int j = (int)s.size() - 1;. The bug is an off-by-one error: the last valid index is one less than the size. Every palindrome that is not empty will fail the same way, so the wrong result on a tells you where to look.

The general method for this kind of bug is to choose the smallest input that fails, trace the first iteration of the loop with real numbers, and compare each variable with what it should be. Here the trace shows j equal to 1 for a one-letter word, which is the wrong index immediately.

Variations and edge cases

Palindrome numbers. Convert the number to text with to_string, then run the two-pointer check on the text. Negative numbers are not palindromes if the minus sign is kept, because the sign has no mirror.

Longest palindromic substring. Choose a centre, which is either one character or the gap between two characters, and expand outward while the characters on both sides match. Try every centre. This takes O(n squared) time, which is fast enough for n up to a few thousand. The practice section asks you to build it.

Anagram of a substring. The question "does any substring of s have the same letters as p" uses a fixed-size window that slides across the text, with 26 counters for the window and for p. That is the sliding window pattern from the next lesson.

Permutation check. Anagrams of the same length are permutations of each other. The same methods apply.

Palindrome by rearrangement. A question may ask whether the letters of a word can be rearranged into a palindrome. The counter method answers it with little extra work. In a palindrome, every letter appears in mirror pairs, except possibly one letter in the middle when the length is odd. So the answer is yes exactly when at most one letter has an odd count. For aabb every count is even, and abba is one arrangement. For aab only b has an odd count, and aba is one arrangement. For abc three letters have odd counts, so no arrangement works.

Interview and real-world use

Interviewers ask palindrome questions because they reveal your habits. A strong answer names the pattern before writing code, states the edge cases, gives the complexity, and tests the empty string and a one-letter string. Say "two pointers, O(n) time, O(1) space" in the first minute, then code.

Anagram questions appear in search, spell checking and data cleaning. A search system might group words that are anagrams to suggest alternatives. A data pipeline might compare two lists of tags while ignoring their order. The sorted key from example 4 is the standard way to group records, and the counter method is the standard way to compare two of them quickly.

Practice

Exercise 1: Palindrome for strings with spaces

Write bool isPalindromeSpaces(const string& s) that ignores spaces only and is case sensitive. Test it on race car (true) and race a car (false).

#include <string>
using namespace std;
 
bool isPalindromeSpaces(const string& s) {
    int i = 0;
    int j = (int)s.size() - 1;
    while (i < j) {
        while (i < j && s[i] == ' ') i++;
        while (i < j && s[j] == ' ') j--;
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}

Exercise 2: Longest palindromic substring

Write int longestPalindrome(const string& s) that returns the length of the longest palindromic substring. Expand around each centre. Test babad (answer 3) and cbbd (answer 2).

#include <algorithm>
#include <string>
using namespace std;
 
int expand(const string& s, int l, int r) {
    while (l >= 0 && r < (int)s.size() && s[l] == s[r]) {
        l--;
        r++;
    }
    return r - l - 1;
}
 
int longestPalindrome(const string& s) {
    int best = 0;
    for (int c = 0; c < (int)s.size(); c++) {
        int odd = expand(s, c, c);
        int even = expand(s, c, c + 1);
        best = max(best, max(odd, even));
    }
    return best;
}

Exercise 3: Anagrams with capitals ignored

Write bool anagramIgnoreCase(const string& a, const string& b) that returns true when the words are anagrams, ignoring case. Test Listen and silent (true).

#include <cctype>
#include <string>
#include <vector>
using namespace std;
 
bool anagramIgnoreCase(const string& a, const string& b) {
    if (a.size() != b.size()) return false;
    vector<int> count(26, 0);
    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;
}

Exercise 4: Predict the result

What does isPalindrome("") return with the code from example 1? Explain in one sentence why.

Exercise 5: Count the steps

For the text abcdcba, how many character comparisons does the two-pointer check make before it returns true? Work out the answer, then check your count by tracing.

Exercise 6: Palindrome with a deletion, for a list of words

Write a program that reads words until the end of input and prints YES for each word that becomes a palindrome after deleting at most one letter. Use canBecomePalindrome from the one-deletion program in this lesson, copied into your program. Type abca abc and check that the output is YES then NO.

#include <iostream>
#include <string>
using namespace std;
 
bool isPalindromeRange(const string& s, int i, int j) {
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}
 
bool canBecomePalindrome(const string& s) {
    int i = 0;
    int j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) {
            return isPalindromeRange(s, i + 1, j) || isPalindromeRange(s, i, j - 1);
        }
        i++;
        j--;
    }
    return true;
}
 
int main() {
    string word;
    while (cin >> word) {
        cout << (canBecomePalindrome(word) ? "YES" : "NO") << endl;
    }
    return 0;
}

Exercise 7: Find the anagram pairs in a list

Write a program that reads a line of words and prints the number of pairs of words that are anagrams of each other. Use the sorted-word key and a map<string, int> that counts how many words share each key. For a group of size k, add k times (k minus 1) divided by 2 to the total. Type listen silent enlist cat act tac dog and the output is 6.

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;
 
int main() {
    string w;
    map<string, int> groupSize;
    while (cin >> w) {
        string key = w;
        sort(key.begin(), key.end());
        groupSize[key]++;
    }
    long long pairs = 0;
    for (const auto& entry : groupSize) {
        long long k = entry.second;
        pairs += k * (k - 1) / 2;
    }
    cout << pairs << endl;
    return 0;
}

Exercise 8: Find the mismatch

Two palindromes are compared by a student, who writes if (s[i] == s[j]) and return true inside the loop, and returns true on the first match. Explain what is wrong and fix it.

Exercise 9: Check a number as a palindrome

Write bool isPalindromeNumber(int n) that returns true when a non-negative integer reads the same backwards. Use to_string and the two-pointer method. Test 12321 (true) and 120 (false).

#include <string>
using namespace std;
 
bool isPalindromeNumber(int n) {
    if (n < 0) return false;
    string s = to_string(n);
    int i = 0;
    int j = (int)s.size() - 1;
    while (i < j) {
        if (s[i] != s[j]) return false;
        i++;
        j--;
    }
    return true;
}

Exercise 10: Group by letter count

Write a function vector<string> sameLetters(const vector<string>& words) that returns, in order, the words that have exactly the same letter counts as the first word in the list. Test it on ["listen", "silent", "tinsel", "cat"]. The result is listen, silent and tinsel.

#include <string>
#include <vector>
using namespace std;
 
vector<int> signature(const string& s) {
    vector<int> count(26, 0);
    for (char c : s) count[c - 'a']++;
    return count;
}
 
vector<string> sameLetters(const vector<string>& words) {
    vector<string> out;
    if (words.empty()) return out;
    vector<int> target = signature(words[0]);
    for (const string& w : words) {
        if (signature(w) == target) out.push_back(w);
    }
    return out;
}

Exercise 11: Check two strings with a hash map and a skip

Write bool sameAfterCleaning(const string& a, const string& b) that returns true when a and b have the same letters once spaces are removed and case is ignored. Test Dormitory and dirty room (true).

#include <algorithm>
#include <cctype>
#include <string>
using namespace std;
 
string cleaned(const string& s) {
    string out;
    for (char c : s) {
        if (c != ' ') out += (char)tolower((unsigned char)c);
    }
    sort(out.begin(), out.end());
    return out;
}
 
bool sameAfterCleaning(const string& a, const string& b) {
    return cleaned(a) == cleaned(b);
}

Exercise 12: Explain the complexity

A teammate says their anagram check is O(n squared) because it has two nested loops. Explain why they might be wrong, using the 26-counter method as the example.

What you now know

• A palindrome check uses two pointers that start at the ends and move inward. It runs in O(n) time with O(1) extra space.
• Cleaning a sentence means skipping characters that do not count, with an inner loop, and lower-casing the rest. Cast each char to unsigned char before the <cctype> calls.
• If one mismatch is allowed, test the two ranges that a single deletion could produce.
• Anagrams have three methods: sort both words, use 26 counters for lowercase letters, or use a hash map for any characters.
• A map keyed by a sorted word groups anagrams together. The key is the value every anagram shares.
• Check the empty string, the one-letter string and the case rule before you write code, and say them out loud in an interview.
• The next lesson uses sliding windows and stacks on longer, more realistic string problems.