Palindrome Detection

Algorithms for detecting and working with palindromic strings.

Overview

Multiple approaches for palindrome detection and analysis:

Two-pointer technique: Most efficient for basic palindrome checking
Recursive approach: Elegant solution for educational purposes
Dynamic Programming: For finding palindromic substrings and related problems
Manacher's Algorithm: Linear time palindrome detection

Usage

from algo.algorithms.strings.palindrome import *

# Basic palindrome check
is_palindrome_two_pointer("racecar")  # Returns True
is_palindrome_two_pointer("hello")    # Returns False

# Find all palindromic substrings
# Returns ["a", "ana", "anana", "b", "n"]
palindromes = palindromic_substrings("banana")  

# Using specific strategies
is_palindrome_recursive("kayak")
is_palindrome_dp("level")

Performance

Two-pointer method: O(n) time, O(1) space
Recursive approach: O(n) time, O(n) space due to recursion stack
Dynamic Programming: O(n²) time, O(n²) space
Manacher's Algorithm: O(n) time, O(n) space

API Reference

Palindrome Detection Algorithms

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward. This module implements multiple approaches to detect palindromes in strings:

Two-pointer approach (most efficient)
Recursive approach (elegant but uses more stack space)
Dynamic programming approach (for substring palindrome queries)
Preprocessing with case/space handling
Longest palindromic substring detection

Time Complexities:

Two-pointer: O(n) - linear time, O(1) space
Recursive: O(n) - linear time, O(n) space (call stack)
Dynamic Programming: O(n²) - for preprocessing, O(1) for queries
Longest palindromic substring: O(n²) or O(n) with Manacher's algorithm

`count_palindromic_substrings(s)`

Count the total number of palindromic substrings in a string.

Uses expand around centers approach to count all palindromes.

Time Complexity: O(n²) - expand around each possible center

Space Complexity: O(1) - constant extra space

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`int`	Total count of palindromic substrings

Examples:

>>> count_palindromic_substrings("abc")
3
>>> count_palindromic_substrings("aaa")
6

`is_palindrome_dp(s, start, end, dp)`

Check if a substring is a palindrome using preprocessed DP table.

Time Complexity: O(1) - constant time lookup

Space Complexity: O(1) - no additional space

Parameters:

Name	Type	Description	Default
`s`	`str`	Original string	required
`start`	`int`	Start index of substring	required
`end`	`int`	End index of substring (inclusive)	required
`dp`	`List[List[bool]]`	Preprocessed DP table from preprocess_palindrome_dp	required

Returns:

Type	Description
`bool`	True if substring s[start:end+1] is a palindrome

Examples:

>>> s = "racecar"
>>> dp = preprocess_palindrome_dp(s)
>>> is_palindrome_dp(s, 0, 6, dp)
True
>>> is_palindrome_dp(s, 1, 5, dp)
True

`is_palindrome_permutation(s)`

Check if any permutation of the string can form a palindrome.

A string can form a palindrome if at most one character has an odd frequency.

Time Complexity: O(n) - single pass to count frequencies Space Complexity: O(k) where k is number of unique characters

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`bool`	True if some permutation of s can form a palindrome

Examples:

>>> is_palindrome_permutation("aab")
True
>>> is_palindrome_permutation("abc")
False
>>> is_palindrome_permutation("aabbcc")
True

`is_palindrome_recursive(s, start=None, end=None)`

Check if a string is a palindrome using recursion.

This approach uses recursion to check characters from both ends, moving inward until the middle is reached.

Time Complexity: O(n) - each character checked once

Space Complexity: O(n) - recursion call stack

Parameters:

Name	Type	Description	Default
`s`	`str`	String to check	required
`start`	`int`	Starting index (used internally for recursion)	`None`
`end`	`int`	Ending index (used internally for recursion)	`None`

Returns:

Type	Description
`bool`	True if the string is a palindrome, False otherwise

Examples:

>>> is_palindrome_recursive("level")
True
>>> is_palindrome_recursive("python")
False

`is_palindrome_two_pointer(s, case_sensitive=True, ignore_spaces=False)`

Check if a string is a palindrome using two-pointer technique.

This is the most efficient approach, using two pointers that move towards each other from both ends of the string.

Time Complexity: O(n) - single pass through string

Space Complexity: O(1) - constant extra space

Parameters:

Name	Type	Description	Default
`s`	`str`	String to check	required
`case_sensitive`	`bool`	Whether to consider case differences	`True`
`ignore_spaces`	`bool`	Whether to ignore whitespace and punctuation	`False`

Returns:

Type	Description
`bool`	True if the string is a palindrome, False otherwise

Examples:

>>> is_palindrome_two_pointer("racecar")
True
>>> is_palindrome_two_pointer("hello")
False
>>> is_palindrome_two_pointer("A man a plan a canal Panama", False, True)
True

`longest_palindromic_substring_dp(s)`

Find the longest palindromic substring using dynamic programming.

Uses the DP table approach to find all palindromes and return the longest.

Time Complexity: O(n²) - build DP table

Space Complexity: O(n²) - DP table storage

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`str`	Longest palindromic substring

Examples:

>>> longest_palindromic_substring_dp("babad")
'bab'
>>> longest_palindromic_substring_dp("cbbd")
'bb'

`longest_palindromic_substring_expand(s)`

Find the longest palindromic substring using expand around centers.

For each possible center (character or between characters), expand outward while characters match to find palindromes.

Time Complexity: O(n²) - O(n) centers, O(n) expansion each

Space Complexity: O(1) - constant extra space

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`str`	Longest palindromic substring

Examples:

>>> longest_palindromic_substring_expand("babad")
'bab'
>>> longest_palindromic_substring_expand("cbbd")
'bb'

`longest_palindromic_substring_manacher(s)`

Find the longest palindromic substring using Manacher's algorithm.

This implementation uses a linear time approach by utilizing previously computed palindrome information to avoid redundant comparisons.

Time Complexity: O(n) - linear time, much faster than O(n²) approaches

Space Complexity: O(n) - for transformed string and P array

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`str`	Longest palindromic substring

Examples:

>>> longest_palindromic_substring_manacher("babad")
'bab'
>>> longest_palindromic_substring_manacher("cbbd")
'bb'

`longest_palindromic_substring_naive(s)`

Find the longest palindromic substring using naive approach.

Checks every possible substring to find the longest palindrome.

Time Complexity: O(n³) - O(n²) substrings, O(n) to check each

Space Complexity: O(1) - constant extra space

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`str`	Longest palindromic substring

Examples:

>>> longest_palindromic_substring_naive("babad")
'bab'
>>> longest_palindromic_substring_naive("cbbd")
'bb'

`palindromic_substrings(s)`

Find all palindromic substrings in a string.

Returns a list of all unique palindromic substrings.

Time Complexity: O(n²) for finding + O(k) for storing, where k is number of palindromes Space Complexity: O(k) where k is number of unique palindromes

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`List[str]`	List of all unique palindromic substrings

Examples:

>>> sorted(palindromic_substrings("aab"))
['a', 'aa', 'b']
>>> sorted(palindromic_substrings("abc"))
['a', 'b', 'c']

`preprocess_palindrome_dp(s)`

Preprocess a string to create a DP table for palindrome substring queries.

Creates a 2D table where dp[i][j] indicates if substring s[i:j+1] is a palindrome. This allows O(1) palindrome queries for any substring after O(n²) preprocessing.

Time Complexity: O(n²) - fill entire DP table

Space Complexity: O(n²) - 2D DP table

Parameters:

Name	Type	Description	Default
`s`	`str`	String to preprocess	required

Returns:

Type	Description
`List[List[bool]]`	2D boolean table for palindrome queries

Examples:

>>> dp = preprocess_palindrome_dp("abcba")
>>> dp[0][4]  # Check if entire string is palindrome
True
>>> dp[1][3]  # Check if "bcb" is palindrome
True

`shortest_palindrome(s)`

Find the shortest palindrome by adding characters to the front.

Finds the longest prefix that is also a suffix when reversed, then adds the remaining suffix (reversed) to the front.

Time Complexity: O(n²) - KMP-like approach can make it O(n) Space Complexity: O(n) - for creating the result string

Parameters:

Name	Type	Description	Default
`s`	`str`	Input string	required

Returns:

Type	Description
`str`	Shortest palindrome formed by adding characters to front

Examples:

>>> shortest_palindrome("aacecaaa")
'aaacecaaa'
>>> shortest_palindrome("abcd")
'dcbabcd'