Palindrome: What It Is, Palindrome Words and How to Check Your Own

The English word "level" reads the same from left to right and from right to left, and that is usually where the curiosity starts. Now take a whole phrase: "never odd or even". It also reads the same both ways, but only if you first throw away the spaces. That single detail is the whole difference between a strict palindrome and a normalized one, and it explains most of the arguments people have about the topic.

What a palindrome is, strictly speaking

Formally, a palindrome is a string in which the character at position i matches the character at position n-1-i for every i. Put another way, the string equals its own reversal. The definition says nothing about words, languages or sentences: it works on any characters at all, spaces and punctuation included. If the string does not match its inverse, it is not a palindrome, whatever the topic of the surrounding text might suggest.

• "level" has five letters, the outer pair matches and the middle letter matches itself;
• "rotor" has five letters with the second and fourth identical;
• "racecar" reads the same in both directions, seven letters including the middle one;
• "never odd or even" is fourteen letters once the spaces are gone;
• "Was it a car or a cat I saw" is a full sentence that survives normalization.

Checking a short word by hand takes seconds. It gets awkward once you want more than a yes or no answer, for instance when the interesting question is where exactly the symmetry breaks. That is where normalization has to be spelled out.

Normalization: spaces, punctuation and case

The everyday definition of a palindrome is far looser than the formal one. Nobody seriously argues that "Never odd or even" stops being a palindrome because of capital letters and spaces. So text is cleaned up before comparison, and it matters which rules are applied.

• spaces: "never odd or even" turns into "neveroddoreven", fourteen characters;
• punctuation: a question mark or a period is dropped and the remaining letters are compared;
• case: the leading capital and the small letter at the end are both lowered, and the symmetry becomes exact;
• digits and letters of other scripts are kept, so the Chinese phrase 上海自來水來自海上 counts as well.

Normalization is part of the definition, not a decoration. Drop the spaces but keep the case and "Never odd or even" fails immediately: the two ends are "n" and "n" but the second pair compares "e" with "e" only after lowercasing, and a single stray capital in the middle breaks the whole thing. That is why checking tools expose the normalization rules as separate switches rather than burying them in the code.

Palindrome words worth remembering

Short palindrome words are easy to collect. Three-letter examples are "did", "gig", "bob", "pip", "eve", "bib", "mom", "dad", "nun", "pep" and "wow". Five-letter ones include "level", "radar", "rotor", "civic", "kayak", "refer", "tenet", "madam" and "solos". Two-letter palindromes exist too, but there are only so many: "aa", "bb", "oo" and a handful more.

level               → level              (5 characters)
rotor               → rotor              (5 characters)
civic               → civic              (5 characters)
never odd or even   → neveroddoreven     (14 characters)
Was it a car or a cat I saw
                    → wasitacaroracatisaw (19 characters)
上海自來水來自海上      → 上海自來水來自海上        (9 characters)

A single letter is always a palindrome, since it has nothing to compare against. That is also why long phrases are impressive. For a random string of twenty characters drawn from a 26-letter alphabet the chance of an exact match is one in 26 to the power of ten, which is roughly one in 141 trillion.

Checking a string: from both ends toward the middle

You do not need a library or a regular expression to check a palindrome. Two indices are enough: one starts at the first character, the other at the last, and they walk toward each other. At every step the two characters are compared, and the moment they differ the answer is settled.

1. normalize the string according to the rules you chose: strip spaces and punctuation, lowercase if needed;
2. put the left index on the first character and the right index on the last;
3. while the indices have not crossed, compare the character on the left with the character on the right;
4. on the first mismatch, remember the position: that is where the symmetry broke;
5. if every pair matched, the string is a palindrome, and the single middle character always matches itself.

Step 0. Normalization: drop the spaces → neveroddoreven (14 characters)

Step 1. n vs n   positions 1 and 14   matched
Step 2. e vs e   positions 2 and 13   matched
Step 3. v vs v   positions 3 and 12   matched
Step 4. e vs e   positions 4 and 11   matched
Step 5. r vs r   positions 5 and 10   matched
Step 6. o vs o   positions 6 and 9    matched
Step 7. d vs d   positions 7 and 8    matched

The indices met in the middle, every pair matched → palindrome

Run the same routine over "notapalinindrome" and the very first pair already fails, "n" against "t". A good checker does not merely report failure, it points at the position of the first mismatch and shows the two characters that disagreed, which saves counting the string by hand.

Manacher algorithm: every palindrome in one pass

Comparing from both ends answers whether the whole string is a palindrome. The harder question is which palindromes live inside it. Testing every substring separately costs roughly n squared over two comparisons for a string of length n. Manacher algorithm finds all of them in linear time.

The trick is to compute, for every position, the radius of the largest palindrome centered there. Odd and even radii are handled separately: in the first case the center is a character, in the second it is the gap between two neighbours. The algorithm remembers the right border of the palindrome it has already found, and when it lands inside that border it copies the radius from the mirrored position instead of comparing characters again.

def manacher(s):
    n = len(s)
    d1 = [0] * n          # odd-length palindromes
    d2 = [0] * n          # even-length palindromes
    l, r = 0, -1
    for i in range(n):
        k = 1 if i > r else min(d1[l + r - i], r - i + 1)
        while i - k >= 0 and i + k < n and s[i-k] == s[i+k]:
            k += 1
        d1[i] = k
        if i + k - 1 > r:
            l, r = i - k + 1, i + k - 1
    l, r = 0, -1
    for i in range(n):
        k = 0 if i > r else min(d2[l + r - i + 1], r - i + 1)
        while i - k - 1 >= 0 and i + k < n and s[i-k-1] == s[i+k]:
            k += 1
        d2[i] = k
        if i + k - 1 > r:
            l, r = i - k, i + k - 1
    return d1, d2

Applied to "abacaba" the odd radii come out as [1, 2, 1, 4, 1, 2, 1]. The 4 in the middle means a palindrome of length 7 fits around the fourth letter, which is the whole string. The even radii are all zero, so this string contains no even-length palindrome. Reconstructing the substrings from those two arrays gives "aba" starting at position 1, "abacaba" starting at position 1 and "aba" starting at position 5.

This is how you find palindromic substrings in bulk, how the longest palindromic substring is solved in linear time, and why checking a document of tens of thousands of characters stays fast.

Palindromic numbers

A number can be a palindrome too, and the definition is easiest here: the digits read the same in both directions. Every single digit number qualifies. There are nine two-digit palindromes, 11, 22 and so on up to 99. Three-digit ones number 90, from 101 to 999, and each of them simply repeats the first digit at the end.

• one digit: nine of them, from 1 to 9;
• two digits: nine, 11, 22, 33, 44, 55, 66, 77, 88, 99;
• three digits: 90, from 101 to 999, following the pattern aba;
• five digits: 900 of them following abcba, from 10001 to 99999, for instance 12321;
• seven digits: the pattern abcdcba, the smallest one being 1000001.

Checking a number uses exactly the same two-index routine as checking a word. To see the symmetry with your own eyes, reverse the text: the reversed digits have to come back identical.

Palindromes in DNA

In biology the word means something slightly different. It is not about a run of letters but about a stretch of DNA on one strand matching the same stretch on the other strand read in the opposite direction. Such sequences are called reverse-complement palindromes, and they are where restriction sites live, the places that bacterial enzymes cut. For a bacterium this is a way to defend its own genome against foreign DNA.

The mechanism is easy to follow: take the sequence, replace the order of the letters with the reverse order using the complementary pairs A with T and G with C, then compare with the original. A match means you have a palindrome.

GAATTC
  complement:       CTTAAG
  reverse order:    GAATTC   ← matches the original

GGATCC
  complement:       CCTAGG
  reverse order:    GGATCC   ← matches the original

Complement rules: A↔T, G↔C

The pair GAATTC is a recognizable one: it is the site cut by the enzyme EcoRI. The match is not a coincidence, sequences of this kind are common in nature precisely because enzymes sit on them.

How to check a piece of text

The practical check takes less than a minute. Open the palindrome checker, paste the string and look at the result: the tool tells you whether it is a palindrome, shows how many characters survived normalization, and points at the position where the characters first disagreed. The three switches above the button control the rules: ignore spaces, ignore punctuation, ignore case.

Two neighbours come in handy as well, the case converter and the text reverser. A useful combination is to reverse the string and compare it with the original: if the reversal matches, you have a palindrome, and if it does not, the reversal shows the mismatch immediately. All the work happens in the browser, so the contents of the field never leave your machine.

One neat side effect of reversible ciphers is worth knowing: any cipher that returns the original text after being applied twice preserves palindromes. That is how the Caesar cipher and ROT13 behave, since "abcba" becomes "nopon" and "nopon" is still a palindrome.

Common questions

Is an empty string a palindrome?

Formally an empty string equals its own reversal, but checking tools treat empty input as "nothing to check" and ask you to type something first. A single character, on the other hand, is always a palindrome, since there is nothing to compare it against.

Is a palindrome the same thing as an anagram?

No. An anagram is a rearrangement of letters that produces a different word, "salt" and "slat" for instance. A palindrome is simpler: it matches itself after being reversed, so "salt" cannot be one in principle.

Are palindromes rare?

For short words they are anything but rare, because only the two outer letters have to agree, which happens about once in twenty-six attempts per pair. The probability falls quickly as the word gets longer. Long palindromes in ordinary text almost always arrive through normalization, in rhyming slogans, names or technical identifiers.

Does palindrome analysis help in cryptography?

Not as a protection method on its own. There is a body of known-plaintext style tests called palindrome cryptanalysis that breaks a cipher by splitting it into palindromic blocks and recovering the key, and it still shows up regularly in university exercises on cryptography. Its practical value is that the palindrome test itself runs in linear time, which makes it a cheap pre-filter.

Should spaces be removed before checking?

It depends on the question. If you are testing whether a brand name or a slogan looks symmetrical to a human, keep the spaces and the punctuation, because otherwise you are comparing something nobody sees. If you are testing the symmetry of the set of letters itself, normalization is mandatory.