Q: Longest palindromic substring — Find the longest palindromic substring in a string.
This is a classic interview problem. It's not something that occurs IRL very much, but it's probably the third most common dynamic programming question after Fibbonacci and the knapsack problem. Every palindrome of length $n$ contains palindromes of length $n/2$ and smaller inside. So to brute force this problem, search for all of the palindromes of length 2 or 3 and grow them outwards.
import unittest
class TestP(unittest.TestCase):
"""Example of how to use unittest in Jupyter."""
def testEmptyString(self):
self.assertEqual(p(""), "")
def testUnitStringP(self):
self.assertEqual(p("A"), "A")
def testStartP(self):
self.assertEqual(p("AABB"), "AA")
def testEndP(self):
self.assertEqual(p("ABCC"), "CC")
def testMidP(self):
self.assertEqual(p("ACCB"), "CC")
def testOddP(self):
self.assertEqual(p("ABCDQQQABCD"), "QQQ")
if __name__ == '__main__':
unittest.main(argv=[''], exit=False)
...... ---------------------------------------------------------------------- Ran 6 tests in 0.002s OK
Omitted, did this for a coding exercise at RC.
If you draw out an $i-j$ table on paper on an example palindromic string, you will find that the lower triangular is null, whilst the upper triangular is a sequence of boolean values ascending 1,1 upwards and to the right which are always some number of trues followed by some number of falses. So if the $1,2$ entry is true, the $0,3$ entry might be true, but if $1,2$ is false $0,3$ will never be true.
To learn, descend in a zigzag pattern down these array entries and climb outwards. To generate a result, repeat that journey while tallying true lengths. This reduces the problem to solving for these diagonal matrix entries.
function p(s):
table = Array(i=0,...,n-1; j=1,...,n)
len_longest = 1
idx_start_longest = 0
curr = <-1, 1>
next_step = <1, 0>
while(curr[0] < len(s) and curr[1] < len(s)):
curr + curr + next_step
next_step = next_step[::-1]
offset = 0
i, j = curr[0], curr[1]
while s[i:j] = s[i:j:-1]:
offset += 1
i -= 1
j += 1
len = offset[0] + adjustment for even or odd start
if len > len_longest:
len_longest = len
idx_start_longest = i
return s[idx_start_longest:idx_start_longest + len_longest]
def p(s):
if s == "": return ""
len_longest = 1
idx_start_longest = 0
curr = [-1, 1]
next_step = [1, 0]
while max(curr[0], curr[1]) <= len(s):
curr[0], curr[1] = curr[0] + next_step[0], curr[1] + next_step[1]
next_step = tuple(list(next_step)[::-1])
offset = 0
i, j = curr[0], curr[1]
# If our starting point is not already a palindrome, skip this iteration.
# Odd starting points are always palindromic, but even starting points may not be.
if s[i:j] != s[i:j][::-1]:
continue
while s[i - 1:j + 1] == s[i - 1:j + 1][::-1] and i - 1 >= 0 and j + 1 <= len(s):
offset += 1
i -= 1
j += 1
len_current = j - i
if len_current > len_longest:
len_longest = len_current
idx_start_longest = i
return s[idx_start_longest:idx_start_longest + len_longest]