String based:
- Valid Palindrome (Easy)
- Longest Palindrome (Easy)
- Valid Palindrome II (Easy)
- Palindrome Linked List (Easy, still more about linked list)
- Remove Palindromic Subsequences (Easy)
- Find First Palindromic String in the Array (Easy)
- Break a Palindrome (Medium)
- Palindrome Partitioning (Medium, +dp / backtrack)
- Construct K Palindrome Strings (Medium)
- Split Two Strings to Make Palindrome (Medium)
- Can Make Palindrome from Substring (Medium)
- Longest Palindrome by Concatenating Two Letter Words (Medium)
- Palindromic Substrings (Medium, +dp)
- Unique Length-3 Palindromic Subsequences (Medium)
- Longest Palindromic Substring (Medium, +dp)
- Longest Palindromic Subsequence (Medium, +dp)
- Maximum Product of the Length of Two Palindromic Subsequences (Medium, +dp / backtrack)
- Shortest Palindrome (Hard)
- Palindrome Pairs (Hard)
- Palindrome Partitioning II (Hard)
- Palindrome Partitioning III (Hard, +dp)
- Palindrome Partitioning IV (Hard, +dp)
- Longest Chunked Palindrome Decomposition (Hard, +dp)
- Maximize Palindrome Length From Subsequences (Hard, +dp)
- Minimum Number of Moves to Make Palindrome (Hard, +dp)
- Minimum Insertion Steps to Make a String Palindrome (Hard, +dp)
- Count Different Palindromic Subsequences (Hard, +dp)
- Maximum Product of the Length of Two Palindromic Substrings (Hard)
- Count Palindromic Subsequences (Hard, +dp)
Math based:
String / math based:
General hints:
The most obvious palindrome check is to compare the string representation with the notation in reverse order:
def is_pal(x):
return str(x) == str(x)[::-1]
If we are dealing with numbers, then we can check by enumeration of digits. Also a palindrome cannot be a negative number.
def is_pal(x):
cand, reversed_x = x, 0
while x:
last_digit = x % 10
x //= 10
reversed_x = reversed_x * 10 + last_digit
return cand == reversed_x
We can also work only, for example, with the left part of a number / word, since the right part must be identical:
def is_pal(x):
x = str(x)
for i in range(len(x) // 2):
if x[i] != x[~i]:
return False
return True
Сomparing the right and left parts can be very useful when we are faced with the task of iterating over a very large number of values. For example, if we need to find palindromes with a known number of digits (Find Palindrome With Fixed Length), then instead of brute force search, we can directly form palindromes:
def helper(num, digits):
left = str(num)
if digits % 2 == 0:
right = str(num)[::-1]
else:
right = str(num)[:-1][::-1]
return int(left + right)
And some useful properties of numeric palindromes:
- All numbers with one digit are palindromic.
- Every palindrome with an even number of digits is divisible by 11.
- All palindromic square numbers can only start or end with digits 0, 1, 4, 5, 6 or 9.
- There exist no palindromic squares of length 2, 4, 8, 10, 14, 18, 20, 24, 30, 38, 40.
I hope these hints will help to come to good decisions.
If you have useful tips for this type of tasks, leave them in the comments, we will gradually supplement the post.