Palindrome Algorithms

Overview

Palindrome algorithms identify sequences that read identically forward and backward. A palindrome exhibits perfect symmetry around its center point, making these algorithms fundamental for pattern recognition, data validation, and string manipulation tasks. The term originates from the Greek "palindromos" meaning "running back again."

Palindrome detection appears in diverse contexts including DNA sequence analysis, data integrity verification, linguistic processing, and compression algorithms. The core challenge involves comparing characters or elements from opposing ends of a sequence while moving toward the center, determining whether corresponding positions contain matching values.

Algorithms for palindrome detection range from naive string reversal to optimized bidirectional scanning. Each approach trades off between implementation simplicity, memory consumption, and execution speed. The choice of algorithm depends on input characteristics including sequence length, character encoding, case sensitivity requirements, and whether partial palindrome detection is needed.

# Simple palindrome: exact reversal
"racecar".reverse == "racecar"
# => true

# Longer palindrome with spaces
"A man a plan a canal Panama".downcase.gsub(/\s/, '').reverse
# => "amanaplanacanalpanama"

Palindrome algorithms extend beyond simple equality checks. Advanced applications include finding the longest palindromic substring within a sequence, counting distinct palindromic subsequences, and validating palindromic properties in linked lists or trees. These variations require different algorithmic strategies and data structure considerations.

Key Principles

Palindrome detection relies on symmetry verification through position-wise comparison. The fundamental principle involves comparing elements at distance i from the start with elements at distance i from the end, continuing until reaching the sequence midpoint. For a sequence of length n, positions i and n-1-i must contain identical values for all valid index positions.

The bidirectional scanning principle forms the basis for efficient palindrome checking. Rather than creating a reversed copy and comparing entire sequences, algorithms examine corresponding positions simultaneously. This approach terminates early upon finding the first mismatch, providing significant performance benefits for non-palindromic inputs.

Center expansion represents an alternative principle where validation starts from a potential palindrome center and expands outward. This technique proves particularly effective for finding palindromic substrings, as each position can serve as a potential center. Odd-length palindromes have a single center character, while even-length palindromes have a center between two characters.

# Bidirectional principle
def palindrome_bidirectional?(str)
  left = 0
  right = str.length - 1
  
  while left < right
    return false if str[left] != str[right]
    left += 1
    right -= 1
  end
  
  true
end

Character normalization forms a critical principle when working with real-world text. Case-insensitive palindrome detection requires converting all characters to a consistent case before comparison. Punctuation and whitespace handling introduces additional complexity, as phrases like "A man, a plan, a canal: Panama" constitute valid palindromes when non-alphanumeric characters are excluded.

The substring palindrome principle extends basic detection to find palindromic sequences within larger strings. This requires checking multiple potential starting positions and lengths, significantly increasing computational complexity. Dynamic programming techniques optimize this process by storing intermediate results and avoiding redundant comparisons.

Boundary conditions require special attention in palindrome algorithms. Empty strings and single-character sequences are trivially palindromic. Zero-length and one-character comparisons return true without iteration. Off-by-one errors frequently occur when calculating midpoint positions, particularly for even-length sequences where no single center character exists.

Implementation Approaches

The reversal comparison approach creates a reversed copy of the input sequence and checks equality with the original. This strategy offers maximum simplicity and readability but incurs additional memory allocation proportional to input size. The approach performs well for small sequences where memory overhead remains negligible and code clarity takes precedence.

# Reversal approach
def palindrome_reversal?(str)
  str == str.reverse
end

Bidirectional pointer scanning eliminates memory overhead by comparing characters from opposite ends without creating intermediate data structures. Two pointers start at sequence boundaries and move toward the center, comparing characters at each step. The algorithm terminates when pointers meet or cross, or when a mismatch is detected. This approach provides optimal space complexity at O(1) while maintaining O(n) time complexity.

Recursive decomposition breaks palindrome checking into smaller subproblems. The base case handles sequences of length zero or one, returning true immediately. The recursive case compares first and last characters, then recursively validates the remaining substring with boundaries narrowed by one position on each end. While conceptually elegant, recursion introduces function call overhead and risks stack overflow for very long sequences.

# Recursive approach
def palindrome_recursive?(str, left = 0, right = str.length - 1)
  return true if left >= right
  return false if str[left] != str[right]
  palindrome_recursive?(str, left + 1, right - 1)
end

The center expansion approach works bidirectionally from potential palindrome centers. For each position in the input, the algorithm attempts to expand a palindrome by comparing adjacent characters moving outward. This technique excels at finding the longest palindromic substring, as it naturally tracks expansion distance. Each position requires checking for both odd-length palindromes (single center) and even-length palindromes (center between characters).

Dynamic programming solutions build a table storing palindrome validation results for all possible substrings. A boolean matrix dp[i][j] indicates whether the substring from index i to j forms a palindrome. The algorithm fills this table bottom-up, using previously computed results for smaller substrings. This approach supports multiple queries on the same input efficiently but requires O(n²) space and preprocessing time.

Ruby Implementation

Ruby's String class provides built-in methods that simplify palindrome implementation. The reverse method creates a new string with characters in reversed order, enabling straightforward equality comparison. Character access through bracket notation allows direct position-based comparisons without explicit array conversion.

# Using String#reverse
def palindrome?(str)
  str == str.reverse
end

# Case-insensitive with character filtering
def palindrome_normalized?(str)
  clean = str.downcase.scan(/[a-z0-9]/).join
  clean == clean.reverse
end

# Usage
palindrome_normalized?("A man, a plan, a canal: Panama")
# => true

The each_char iterator provides character-by-character enumeration without creating intermediate arrays. Combined with with_index, this enables position-aware palindrome checking while maintaining Ruby idioms. The chars method converts strings to character arrays when array operations are preferred over string indexing.

# Using iterators
def palindrome_iterative?(str)
  str.chars.each_with_index do |char, i|
    return false if char != str[str.length - 1 - i]
    break if i >= str.length / 2
  end
  true
end

Ruby's regular expressions excel at character filtering for normalized palindrome checking. The scan method with alphanumeric patterns extracts valid characters, while gsub removes unwanted elements. The tr method provides efficient character translation for case normalization or character set mapping.

# Advanced normalization
class PalindromeChecker
  def initialize(case_sensitive: false, alphanumeric_only: true)
    @case_sensitive = case_sensitive
    @alphanumeric_only = alphanumeric_only
  end
  
  def palindrome?(str)
    normalized = normalize(str)
    normalized == normalized.reverse
  end
  
  private
  
  def normalize(str)
    result = str
    result = result.downcase unless @case_sensitive
    result = result.scan(/[a-z0-9]/i).join if @alphanumeric_only
    result
  end
end

checker = PalindromeChecker.new(case_sensitive: false)
checker.palindrome?("Race Car")
# => true

Range objects combined with each or step enable elegant bidirectional iteration. The range (0...str.length/2) covers exactly half the string, automatically handling both odd and even lengths. The step method with negative increment provides reverse iteration without explicit index manipulation.

# Using ranges for bidirectional checking
def palindrome_range?(str)
  (0...str.length / 2).all? do |i|
    str[i] == str[str.length - 1 - i]
  end
end

For finding palindromic substrings, Ruby's string slicing with [start, length] or [range] notation extracts substrings efficiently. The each_cons method on character arrays enables sliding window operations useful for palindrome detection in streams or large datasets.

# Finding longest palindromic substring
def longest_palindrome(str)
  return str if str.length < 2
  
  longest = str[0]
  
  str.length.times do |center|
    # Odd length palindromes
    odd = expand_from_center(str, center, center)
    # Even length palindromes
    even = expand_from_center(str, center, center + 1)
    
    current = odd.length > even.length ? odd : even
    longest = current if current.length > longest.length
  end
  
  longest
end

def expand_from_center(str, left, right)
  while left >= 0 && right < str.length && str[left] == str[right]
    left -= 1
    right += 1
  end
  
  str[left + 1...right]
end

longest_palindrome("babad")
# => "bab" or "aba"

Common Patterns

The two-pointer pattern dominates palindrome algorithms due to its efficiency and clarity. Initialize left pointer at index zero and right pointer at the last index. Compare characters at these positions, then increment left and decrement right until pointers converge. This pattern adapts to various palindrome problems including linked lists, where pointers become node references.

# Two-pointer pattern
def palindrome_two_pointer?(str)
  left = 0
  right = str.length - 1
  
  while left < right
    return false unless str[left] == str[right]
    left += 1
    right -= 1
  end
  
  true
end

The expand-around-center pattern handles palindromic substring discovery. Treat each position as a potential palindrome center, expanding outward while characters match. This requires checking both odd-length palindromes (single center) and even-length palindromes (center between two characters). The pattern naturally tracks palindrome length during expansion.

# Expand-around-center pattern
def count_palindromic_substrings(str)
  count = 0
  
  str.length.times do |i|
    # Odd length
    count += expand_count(str, i, i)
    # Even length
    count += expand_count(str, i, i + 1)
  end
  
  count
end

def expand_count(str, left, right)
  count = 0
  
  while left >= 0 && right < str.length && str[left] == str[right]
    count += 1
    left -= 1
    right += 1
  end
  
  count
end

count_palindromic_substrings("aaa")
# => 6 (a, a, a, aa, aa, aaa)

The filter-first pattern separates normalization from palindrome checking. Extract valid characters into a new sequence before applying palindrome algorithms. This separation improves code maintainability and allows reusing palindrome logic across different filtering requirements.

# Filter-first pattern
def valid_palindrome?(str)
  filtered = str.downcase.chars.select { |c| c =~ /[a-z0-9]/ }.join
  palindrome_simple?(filtered)
end

def palindrome_simple?(str)
  str == str.reverse
end

The memoization pattern optimizes repeated palindrome queries on the same input. Store validation results for substrings in a hash or matrix, consulting cached results before performing comparisons. This pattern trades memory for speed when checking multiple substring ranges within a single input.

# Memoization pattern for substring palindromes
class PalindromeCache
  def initialize(str)
    @str = str
    @cache = {}
  end
  
  def palindrome?(start, finish)
    key = [start, finish]
    return @cache[key] if @cache.key?(key)
    
    @cache[key] = compute_palindrome(start, finish)
  end
  
  private
  
  def compute_palindrome(start, finish)
    return true if start >= finish
    
    if @str[start] != @str[finish]
      false
    else
      start + 1 >= finish - 1 || palindrome?(start + 1, finish - 1)
    end
  end
end

Practical Examples

Document validation often requires palindrome checking for codes or identifiers. Certain product codes, reference numbers, or checksums use palindromic formats for error detection. The validation must handle various input formats while maintaining accuracy.

# Product code validation
class ProductCodeValidator
  CODE_FORMAT = /\A[A-Z0-9]{6}\z/
  
  def self.valid_palindrome_code?(code)
    return false unless code.match?(CODE_FORMAT)
    
    normalized = code.upcase
    normalized == normalized.reverse
  end
end

ProductCodeValidator.valid_palindrome_code?("ABC321")
# => false

ProductCodeValidator.valid_palindrome_code?("ABA1ABA")
# => false (wrong length)

ProductCodeValidator.valid_palindrome_code?("123321")
# => true

Text processing applications identify palindromic words or phrases in natural language. This requires sophisticated normalization to handle punctuation, whitespace, and case variations. The processor must distinguish between strict palindromes and those allowing character filtering.

# Palindromic word finder
class PalindromeWordFinder
  def find_palindrome_words(text)
    words = text.split(/\s+/)
    words.select { |word| palindrome_word?(word) }
  end
  
  def find_palindrome_phrases(text, min_length: 3)
    phrases = extract_phrases(text)
    phrases.select { |phrase| palindrome_phrase?(phrase, min_length) }
  end
  
  private
  
  def palindrome_word?(word)
    clean = word.downcase.gsub(/[^a-z]/, '')
    return false if clean.length < 2
    clean == clean.reverse
  end
  
  def palindrome_phrase?(phrase, min_length)
    clean = phrase.downcase.scan(/[a-z]/).join
    return false if clean.length < min_length
    clean == clean.reverse
  end
  
  def extract_phrases(text)
    # Extract sentences and significant phrases
    text.split(/[.!?]+/).map(&:strip).reject(&:empty?)
  end
end

finder = PalindromeWordFinder.new
finder.find_palindrome_words("A racecar drove to the radar station at noon")
# => ["racecar", "radar", "noon"]

DNA sequence analysis uses palindrome detection for identifying restriction sites and complementary sequences. Biological palindromes differ from textual palindromes as they involve complementary base pairing (A-T, G-C) rather than identical character matching.

# DNA palindrome detection
class DNASequence
  COMPLEMENT = { 'A' => 'T', 'T' => 'A', 'G' => 'C', 'C' => 'G' }
  
  def initialize(sequence)
    @sequence = sequence.upcase
  end
  
  def palindromic?(start, finish)
    substr = @sequence[start..finish]
    substr == reverse_complement(substr)
  end
  
  def find_palindromic_sites(min_length: 4)
    sites = []
    
    (0...@sequence.length).each do |start|
      (start + min_length - 1...@sequence.length).each do |finish|
        if palindromic?(start, finish)
          sites << { start: start, finish: finish, sequence: @sequence[start..finish] }
        end
      end
    end
    
    sites
  end
  
  private
  
  def reverse_complement(seq)
    seq.reverse.chars.map { |base| COMPLEMENT[base] }.join
  end
end

dna = DNASequence.new("GAATTC")
dna.palindromic?(0, 5)
# => true (GAATTC is its own reverse complement)

Performance Considerations

Time complexity for basic palindrome checking is O(n) where n represents the input length. Both reversal and two-pointer approaches examine each character once. The reversal method includes additional overhead from string allocation and copying, while two-pointer scanning performs in-place comparisons without memory allocation.

Space complexity varies significantly between approaches. The reversal method requires O(n) additional space for the reversed copy. Two-pointer and recursive methods operate in O(1) space for iterative versions, though recursive implementations consume O(n) stack space in the worst case. For memory-constrained environments, two-pointer iteration provides the optimal space profile.

# Space-efficient approach
def palindrome_minimal_space?(str)
  (0...str.length / 2).all? { |i| str[i] == str[str.length - 1 - i] }
end

Character normalization significantly impacts performance for real-world text processing. Creating normalized strings through methods like downcase, gsub, or scan allocates new strings and iterates through the input. Combining normalization with palindrome checking in a single pass reduces allocations and improves cache locality.

# Single-pass normalized checking
def palindrome_normalized_efficient?(str)
  left = 0
  right = str.length - 1
  
  while left < right
    # Skip non-alphanumeric from left
    left += 1 until left >= right || str[left] =~ /[a-z0-9]/i
    # Skip non-alphanumeric from right
    right -= 1 until left >= right || str[right] =~ /[a-z0-9]/i
    
    break if left >= right
    
    return false if str[left].downcase != str[right].downcase
    
    left += 1
    right -= 1
  end
  
  true
end

Finding the longest palindromic substring through brute force checking requires O(n³) time: O(n²) possible substrings each requiring O(n) validation. Center expansion reduces this to O(n²) by checking each of the 2n-1 possible centers and expanding in O(n) time. Manacher's algorithm achieves O(n) time complexity through clever reuse of previously computed information, though implementation complexity increases substantially.

Substring palindrome counting exhibits similar complexity patterns. Naive enumeration of all substrings with validation requires O(n³) time. Dynamic programming solutions reduce this to O(n²) time and space by building a table of palindrome results for all substring ranges. This approach excels when multiple queries are performed on the same input.

# Dynamic programming for substring queries
class PalindromeMatrix
  def initialize(str)
    @str = str
    @n = str.length
    @dp = Array.new(@n) { Array.new(@n, false) }
    build_matrix
  end
  
  def palindrome?(start, finish)
    @dp[start][finish]
  end
  
  def count_palindromes
    @dp.flatten.count(true)
  end
  
  private
  
  def build_matrix
    # Single characters are palindromes
    @n.times { |i| @dp[i][i] = true }
    
    # Check two-character sequences
    (@n - 1).times do |i|
      @dp[i][i + 1] = (@str[i] == @str[i + 1])
    end
    
    # Check longer sequences
    (3..@n).each do |length|
      (0..@n - length).each do |start|
        finish = start + length - 1
        @dp[start][finish] = (@str[start] == @str[finish]) && @dp[start + 1][finish - 1]
      end
    end
  end
end

Early termination optimization proves critical for non-palindromic inputs. Bidirectional scanning exits immediately upon finding mismatched characters, providing best-case O(1) performance when the first and last characters differ. This optimization makes palindrome checking practical for filtering large datasets where most inputs fail validation.

Reference

Algorithm Comparison

Common Ruby Methods

Normalization Strategies

Complexity by Problem Type

Edge Cases