# Palindromes

Source: https://www.techinterview.org/post/526332105/palindromes/
Updated: 2026-04-16 · techinterview.org

Problem: this year on October 2, 2001, the date in MMDDYYYY format will be a palindrome (same forwards as backwards).

10/02/2001

when was the last date that this occurred on? (see if you can do it in your head!)

### Solution

olution: we know the year has to be less than 2001 since we already have the palindrome for 10/02. it can’t be any year in 1900 because that would result in a day of 91. same for 1800 down to 1400. it could be a year in 1300 because that would be the 31st day. so whats the latest year in 1300 that would make a month? at first i thought it would be 1321, since that would give us the 12th month, but we have to remember that we want the maximum **year** in the 1300 century with a valid month, which would actually be 1390, since 09/31 is a valid date.

but of course, a question like this wouldn’t be complete without an *aha* factor. and of course, there are not 31 days in september, only 30. so we have to go back to august 08 which means the correct date would be **08/31/1380**.

palindromes also offer another great string question.

write a function that tests for palindromes

`bool isPalindrome( char* pStr )`

if you start a pointer at the beginning and the end of the string and keep comparing characters while moving the pointers closer together, you can test if the string is the same forwards and backwards. notice that the pointers only have to travel to the middle, not all the way to the other end (to reduce redundancy).


```
bool isPalindrome( char* pStr ){  if ( pStr == NULL )   return false;   char* pEnd = pStr;  while ( *pEnd != '' )    pEnd++;   pEnd--;   while(pEnd > pStr)  {    if ( *pEnd != *pStr )      return false;     pEnd--;    pStr++;  }   return true;}
```

thanks to tom for sending me this one! congrats on the wedding…

## 2026 Update: Palindrome Algorithms — From O(n²) to O(n)

Palindrome problems range from basic checks to one of the most elegant O(n) algorithms in computer science (Manacher's). Here's the full progression:


```
# Level 1: Check if string is palindrome — O(n)
def is_palindrome(s: str) -> bool:
    return s == s[::-1]  # Or two-pointer approach

# Level 2: Longest palindromic substring — O(n²) expand-around-center
def longest_palindrome_n2(s: str) -> str:
    def expand(left, right):
        while left >= 0 and right  str:
    # Transform: "abc" → "#a#b#c#" (handles even/odd uniformly)
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n  # p[i] = radius of longest palindrome centered at i
    center = right = 0

    for i in range(n):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])

        # Expand around center i
        while (i + p[i] + 1 = 0 and
               t[i + p[i] + 1] == t[i - p[i] - 1]):
            p[i] += 1

        if i + p[i] > right:
            center, right = i, i + p[i]

    # Find maximum
    max_len = max(p)
    center_idx = p.index(max_len)
    start = (center_idx - max_len) // 2
    return s[start:start + max_len]

# Level 4: Count palindromic substrings — O(n) with Manacher
def count_palindromes(s: str) -> int:
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    center = right = 0
    for i in range(n):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])
        while i + p[i] + 1 = 0 and t[i+p[i]+1] == t[i-p[i]-1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    return sum((r + 1) // 2 for r in p)  # Each radius contributes ceil((r+1)/2) palindromes

# Test
s = "racecar"
print(is_palindrome(s))          # True
print(longest_palindrome_n2("babad"))   # "bab" or "aba"
print(manacher("cbbd"))                 # "bb"
print(count_palindromes("abc"))         # 3 (a, b, c)
print(count_palindromes("aaa"))         # 6 (a, a, a, aa, aa, aaa)
```

**Related problems (LeetCode):** #5 (Longest Palindromic Substring), #9 (Palindrome Number), #125 (Valid Palindrome), #131 (Palindrome Partitioning), #647 (Palindromic Substrings). Manacher's algorithm is a classic "explain the intuition" interview question at Google and Jane Street.