Palindromes
Scenario
You need to verify if a DNA sequence is a perfect mirror image of itself.
Do you reverse the entire sequence and check for equality, or is there a way to halt instantly at the first sign of mismatch?
Why it exists
Problem: A palindrome reads identically forward and backward. The naive approach—duplicating the string, reversing it, and comparing—requires O(N) auxiliary space and always scans the entire string even if it fails immediately.
Naive approach: Return `string == reverse(string)`.
Better idea: Use the two-pointer technique to check symmetry from the outside in. If any character mismatches, halt immediately. This uses O(1) space and optimizes the average-case runtime.
Mental model
Imagine folding a piece of paper in half. For the text to be a palindrome, every letter on the left side must perfectly overlap with the corresponding letter on the right side.
Validating a palindrome uses converging two-pointers checking for equality. Finding the longest palindromic substring requires the inverse: placing pointers at a 'center' and expanding outward until symmetry breaks.
Repeated decision: Do the characters at the two ends match? If yes, move inward; if no, it's not a palindrome.
Explanation
To validate if a string is a palindrome, place a pointer at index 0 and a pointer at N-1. If they match, move inward. If they ever mismatch, return false instantly. If they cross, return true.
A more complex problem is finding the *longest* palindromic substring within a larger text. You cannot easily use outside-in pointers here. Instead, you use the 'Expand Around Center' algorithm.
A palindrome must have a center of symmetry. It's either an odd-length center (a single character, like 'c' in "racecar") or an even-length center (the imaginary gap between two identical characters, like the gap between the 'b's in "abba").
The algorithm iterates through every character in the string, treating it as a potential center. It initializes pointers at the center and expands outward. `left--` and `right++`. As long as the characters match and are within array bounds, the palindrome grows. It checks both odd and even centers for every index, keeping track of the absolute maximum length found.
Key points
- Validation: O(N) Time: Checking if a string is a palindrome takes O(N) time and O(1) space.
- Search: O(N^2) Time: Expanding around 2N-1 potential centers (N odd, N-1 even) takes O(N^2) time.
- Early Exit: Both algorithms halt the exact moment symmetry is broken, saving massive computational cycles on invalid strings.
Pattern: Symmetrical Expansion / Convergence
Recognition cues:
- The problem explicitly mentions 'palindromes'.
- The problem asks for symmetrical patterns or mirror images.
Failure signals
- You are using `[::-1]` in Python to reverse strings for validation.
- When expanding from the center, you forget to check for the even-length (gap) centers.
Engineering examples
Bioinformatics
Identifying gene expression markers in DNA.
Restriction enzymes search for palindromic DNA sequences to cut DNA for genetic cloning. Algorithms mimicking this use palindromic expansion.
Network Data Integrity
Verifying lossless transmission of symmetrical packets.
Symmetry checks validate that the payload structure wasn't corrupted in transit.
When not to use
- You need the absolute optimal runtime for searching massive strings: Expand Around Center takes O(N^2). For truly massive datasets, Manacher's Algorithm can find the longest palindromic substring in O(N) time, though it is exceedingly complex to implement.
Common mistakes
- Failing to sanitize input: Standard palindromes ignore spaces, punctuation, and capitalization. You must skip these non-alphanumeric characters by advancing the pointers inside your while loop.
- Out of bounds on expansion: When expanding from the center, the loop must always check `left >= 0` and `right < length` BEFORE checking if the characters match, or it will throw an error.
Glossary
- center of symmetry
- The exact middle point around which both sides are mirror images of each other.
- computational cycles
- The individual steps of processing power a computer uses to perform a task.
- non-alphanumeric characters
- Symbols like punctuation or spaces that are not letters or numbers.
Recall questions
- Why is two-pointer validation better than reversing the entire string?
- What are the two types of palindromic centers?
- What is the time complexity of the 'Expand Around Center' algorithm?
Questions & answers
Verify if a phrase is a palindrome, ignoring non-alphanumeric characters and casing.
Use two converging pointers. If a pointer sits on a non-alphanumeric character, move it inward until it hits a valid character. Compare the lowercase versions. If they differ, return false.
Approach: Converging pointers with conditional skipping.
Count all palindromic substrings in a given string.
Use the Expand Around Center approach. For each of the 2N-1 centers, expand outwards. Increment a count for each valid expansion.
Approach: Expand Around Center.
Interesting facts
- Manacher's algorithm uses dynamic programming to reuse previously expanded palindrome boundaries, achieving O(N) time complexity for the longest palindrome problem.
Continue learning
Previous: Two Pointers on Strings
Related: Two Pointers on Strings