Palindromes, Substrings and Subsequences

Palindromes, Substrings and Subsequences — Tech Epitome

Substring versus subsequence

This distinction decides which techniques are even available, so it is worth being precise about.

Term	Meaning	Count in a string of length n
Substring	Contiguous run of characters	n(n+1)/2
Subsequence	Characters in order, gaps allowed	2ⁿ

Two words that are easy to confuse and very different.

Checking symmetry

python

1def is_symmetric(text):2    left, right = 0, len(text) - 13    while left < right:4        if text[left] != text[right]:5            return False6        left += 17        right -= 18    return True

Two pointers closing in

The longest symmetric stretch

Generating every substring and testing each is O(n³). But symmetry is a property of a centre, not of a substring — so generate centres instead and grow outward.

Growing from one centre

Input"ABCBA"

centre at CB…B matches
expandA…A matches
expandout of bounds — stop, length 5

Resultthe whole string

python

1def longest_symmetric(text):2    best_start, best_len = 0, 13 4    def expand(left, right):5        nonlocal best_start, best_len6        while left >= 0 and right < len(text) and text[left] == text[right]:7            left -= 18            right += 19        length = right - left - 1   # the loop overshoots by one each side10        if length > best_len:11            best_len, best_start = length, left + 112 13    for i in range(len(text)):14        expand(i, i)       # odd-length centre15        expand(i, i + 1)   # even-length centre16 17    return text[best_start:best_start + best_len]

Expand around 2n-1 centres

Practise

Quick quiz

Substrings, subsequences and symmetry

1A problem asks for the longest subsequence with a property. Why is a sliding window the wrong tool?

Windows only work on numbers

A subsequence need not be contiguous, so a window cannot represent it

Subsequences are always shorter

It is the right tool

2How many centres must you consider to find every palindromic substring by expansion?

2n − 1

n²

log n