Palindrome — SWE Playbook

01 / 05

Introduction

This is a class of very popular interview problems.

A palindrome is defined as a string which is the same reversed.

ie. s == s[::-1].

Palindromes have a very nice recursive structure.

So: 'a', 'aba', 'eee', 'abba' are palindromes. 'Ace' is not a palindrome. (empty string is trivially a palindrome)

A crucial property to know is that palindromes have at most one character of odd frequency count. This is very useful for certain problems.

Iterative Check

pythonREFERENCE

def isPalindrome(self, s: str) -> bool:
    n = len(s)
    i, j = 0, n-1

    while i < j:
        if s[i] != s[j]:
            return False
        i += 1
        j -= 1
    return True

Recursive Check

pythonREFERENCE

def isPalindrome(self, s: str) -> bool:
    if not s: return True
    return s[0] == s[-1] and self.isPalindrome(s[1:-1])

02 / 05

Valid Palindrome Problems

Problems that check if a string is a valid palindrome with various constraints.

WORKED PROBLEMS5

01Valid PalindromeEasy

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Solution 1: Continue on non-alphanumeric

pythonREFERENCE

def isPalindrome(self, s: str) -> bool:
    n = len(s)
    i, j = 0, n-1

    while i < j:
        if not s[i].isalnum():
            i += 1
            continue
        if not s[j].isalnum():
            j -= 1
            continue
        if s[i].lower() != s[j].lower():
            return False
        i += 1
        j -= 1
    return True

Solution 2: Inner while loops

pythonREFERENCE

def isPalindrome(self, s: str) -> bool:
    n = len(s)
    i, j = 0, n-1

    while i < j:
        while i < j and not s[i].isalnum():
            i += 1
        while i < j and not s[j].isalnum():
            j -= 1
        if s[i].lower() != s[j].lower():
            return False
        i += 1
        j -= 1
    return True

TimeO(n)

SpaceO(1)

WHY IT WORKS

We basically use two pointers. We initialize from both ends of the string. We loop while the string is more than 1 character long. We iterate until the left and right pointers are alphanumeric. We then check if the lowercase equivalents are equal, if not this string is not a palindrome. Otherwise these 2 characters match and we continue.

Open practice view →Open original problem ↗

02Valid Palindrome IIEasy

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

pythonREFERENCE

def validPalindrome(self, s: str) -> bool:
    def isPalindrome(i, j):
        while i < j:
            if s[i] != s[j]: return False
            i += 1
            j -= 1
        return True
        # return s[i:j+1] == s[i:j+1][::-1]

    n = len(s)
    i = 0
    j = n-1
    while i < j:
        if s[i] != s[j]:
            return isPalindrome(i+1, j) or isPalindrome(i, j-1)
        i += 1
        j -= 1
    return True

TimeO(n)

SpaceO(1)

WHY IT WORKS

This is a slight modification to the existing algorithm. The idea is we are allowed a single mismatching pair. So we basically compare pairs until we see the first mismatch. (notice that at most 1 means we can also have no mismatches. So if the original string is just a palindrome, the algorithm will default to the same behaviour as the definition)

We have two options, either delete s[i] or s[j]. If we delete s[i] we no longer have any deletions remaining, so we just check if s[i+1:j] (inclusive) is a palindrome. Similarly for if we delete s[j]. We take the or of both cases, ie. if any of them is a palindrome, we can just delete the one that leads to a palindrome.

Open practice view →Open original problem ↗

03Valid Palindrome II - GeneralizedMedium

Generalized version: what about if we want to check if a palindrome can be created with at most k deletions?

pythonREFERENCE

def validPalindrome(self, s: str) -> bool:
    # this is actually O(k) space, since ONCE we see a mismatch, we will go downwards...
    # the cache is actually pointless, we will never re-encounter the same state!!
    # @cache
    def dp(i, j, k):  # true iff s[i:j+1] is a palindrome after deleting at most k characters from it
        if k == 0: return s[i:j+1] == s[i:j+1][::-1]
        if i == j: return True
        while i < j:
            if s[i] != s[j]:
                return dp(i+1, j, k-1) or dp(i, j-1, k-1)
            i += 1
            j -= 1
        return True
    return dp(0, len(s)-1, 1)

TimeO(n^2 * k)

SpaceO(k)

WHY IT WORKS

We can generalize this idea using recursion. Time complexity is O(n^2 * k), with O(k) space (depth of recursive stack).

Note: See LCS section in DP for more palindrome problems.

Open original problem ↗

04Valid Palindrome IIIHard

Given a string s and an integer k, return true if s is a k-palindrome.

A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

pythonREFERENCE

def isValidPalindrome(self, s: str, k: int) -> bool:
    # standard dp(i,j,k) dp will tle O(n^2k)
    # transform into get longest palindromic subsequence
    # reverse problem
    # return if length >= n-k

    # dp: dp(i,j): max palindromic subsequence in s[i:j+1]
    # if i > j: return 0. if i == j: return 1: if s[i] == s[j]: 2 + dp(i+1,j-1)
    # else: return max(dp(i+1,j), dp(i,j-1))

    @cache
    def dp(i, j):
        if i >= j: return i == j
        return 2 + dp(i+1, j-1) if s[i] == s[j] else max(dp(i+1, j), dp(i, j-1))

    return dp(0, len(s)-1) >= len(s)-k

TimeO(n^2)

SpaceO(n^2)

WHY IT WORKS

Note there is actually a linear time solution to this k removals problem using longest palindromic subsequence.

Idea: Think in reverse. If we remove up to k characters, that means the remaining characters must form a palindrome. We can remove characters anywhere in the string, so the remaining characters form a palindromic subsequence. So we just check if the longest palindromic subsequence has length >= n-k, if so we can just remove all indices not in that palindromic subsequence.

Open practice view →Open original problem ↗

05Valid Palindrome IVMedium

You are given a 0-indexed string s consisting of only lowercase English letters. In one operation, you can change any character of s to any other character.

Return true if you can make s a palindrome after performing exactly one or two operations, or return false otherwise.

Two Pointer Solution

pythonREFERENCE

# we can count the number of "mistakes", if there are 1 or 2 mistakes we can fix.
# if there are 3 mistakes we are screwed. if there are 0 mistakes, we can change 2 chars to the same char, so we are fine.
# so just check if < 3 mistakes..

def makePalindrome(self, s: str) -> bool:
    left, right, mistakes = 0, len(s)-1, 0
    while left <= right:
        if s[left] != s[right]:
            mistakes += 1
            if mistakes >= 3: break  # optimization
        left += 1
        right -= 1
    return mistakes < 3

One-liner Solution

pythonREFERENCE

def makePalindrome(self, s: str) -> bool:
    return sum(s[i] != s[len(s)-i-1] for i in range(len(s) // 2)) < 3

TimeO(n)

SpaceO(1)

WHY IT WORKS

Note that this simple 2 pointers works because this is 'changes', and not removals. Removals will require DP because we have 2 options to remove, i or j. In this case of changes, we can choose either one to become the other, it doesn't matter which one we choose and it doesn't change our answer as each pair of indices is independent after matching.

Open practice view →Open original problem ↗

03 / 05

Longest Palindromic Substring

Problems involving finding the longest palindromic substring.

WORKED PROBLEMS2

01Longest Palindromic SubstringMedium

Given a string s, return the longest palindromic substring in s.

DP Solution (O(n²) time, O(n²) space)

We can brute force this problem in O(n³) time and O(1) space. There are O(n²) substrings, and we can verify if it is palindromic in O(n) time.

However, this is clearly wasteful, because of the substructure of palindromes. We are repeatedly checking if the same substrings are palindromic, when we already know whether they are or not. So we can simply cache this using a dp.

pythonREFERENCE

def longestPalindrome(self, s: str) -> str:
    n = len(s)
    @cache
    def dp(i, j):
        if i > j: return True
        return s[i] == s[j] and dp(i+1, j-1)

    res_length = 0
    res = ""
    for i in range(n):
        for j in range(i, n):
            if dp(i, j):
                if j-i+1 > res_length:
                    res_length = j-i+1
                    res = s[i:j+1]
    return res

Expand from Center (O(n²) time, O(1) space)

We can reverse the problem, by thinking about the centres of palindromes. Palindromes can be either even length or odd lengthed. If they are odd lengthed, they have a unique centre. However if they are even length, they have 2 centres. (ie. 'aba', b is the centre. And 'abba', 'bb' are the 2 centres)

The idea is, any palindrome has a centre, so if we try all centres we will visit all palindromes. We start at the centre and expand outwards, once there is a mismatch we know this centre is finished, as any larger string with this centre cannot be a palindrome any longer. (this is greedy thinking)

This is efficient because 1. We don't have to store any extra space and run the risk of MLE. and 2. We do not need any precomputation because we start from the centre instead of the ends, and don't have to search all substrings.

pythonREFERENCE

# time: O(n^2). space: O(1). n = len(s)
def longestPalindrome(self, s: str) -> str:
    res = ""
    n = len(s)

    def expand(i, j):
        nonlocal res
        while 0 <= i and j < n and s[i] == s[j]:
            if j-i+1 > len(res):
                res = s[i:j+1]
            i -= 1
            j += 1

    for i in range(n):
        expand(i, i)      # expand odd length centres
        expand(i, i+1)    # expand even length centres
    return res

TimeO(n²)

SpaceO(1)

WHY IT WORKS

The worst case is when substrings are palindromes: ie. s = 'aaaaaa'...

Note: there is actually an O(n) solution called Manacher's algorithm, but you aren't expected to know it.

Open practice view →Open original problem ↗

02Palindromic SubstringsMedium

Given a string s, return the number of palindromic substrings in it.

Expand from Center Solution

pythonREFERENCE

def countSubstrings(self, s: str) -> int:
    n = len(s)
    res = 0

    def expand(i, j):
        nonlocal res
        while i >= 0 and j < n and s[i] == s[j]:
            res += 1
            i -= 1
            j += 1

    for i in range(n):
        expand(i, i)
        expand(i, i+1)
    return res

DP Solution

pythonREFERENCE

def countSubstrings(self, s: str) -> int:
    n = len(s)
    @cache
    def dp(i, j):
        if i > j: return True
        return s[i] == s[j] and dp(i+1, j-1)
    return sum(dp(i, j) for i in range(n) for j in range(i, n))

TimeO(n²)

SpaceO(1) for expand, O(n²) for DP

WHY IT WORKS

This is the same idea as Longest Palindromic Substring. We can either expand from centers or use DP to count all palindromic substrings.

Open practice view →Open original problem ↗

04 / 05

Palindrome Queries

Problems involving multiple queries about palindrome properties.

WORKED PROBLEMS1

01Can Make Palindrome from SubstringMedium

You are given a string s and array queries where queries[i] = [lefti, righti, ki]. We may rearrange the substring s[lefti...righti] for each query and then choose up to ki of them to replace with any lowercase English letter.

If the substring is possible to be a palindrome string after the operations above, the result of the query is true. Otherwise, the result is false.

Return a boolean array answer where answer[i] is the result of the ith query queries[i].

Note that each letter is counted individually for replacement, so if, for example s[lefti...righti] = "aaa", and ki = 2, we can only replace two of the letters. Also, note that no query modifies the initial string s.

Prefix Frequency Solution

pythonREFERENCE

def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
    cumulative_freq = [Counter()]
    # you can add and subtract counters
    n = len(s)
    for i in range(n):
        cumulative_freq.append(cumulative_freq[-1] + Counter([s[i]]))

    res = []

    for l, r, k in queries:
        freq = cumulative_freq[r+1] - cumulative_freq[l]  # 1 indexed
        min_num_moves_required = sum(f % 2 == 1 for _, f in freq.items()) // 2
        res.append(min_num_moves_required <= k)

    return res

One-liner Solution

pythonREFERENCE

def canMakePaliQueries(self, s: str, queries: List[List[int]]) -> List[bool]:
    cumulative_freq = [Counter()]
    for i in range(len(s)):
        cumulative_freq.append(cumulative_freq[-1] + Counter([s[i]]))

    return [sum(f % 2 == 1 for _, f in (cumulative_freq[r+1] - cumulative_freq[l]).items()) // 2 <= k for l, r, k in queries]

TimeO(n + q * 26)

SpaceO(n * 26)

WHY IT WORKS

Few things:
1. Rearrangement means order doesn't matter. So this means only the frequency count matters.
2. You can add and subtract counters... this is really useful.
3. Use the key property mentioned at the beginning, where palindromes can have at most 1 odd frequency character. So when we have more than 1 odd frequency character, we are forced to use some of our k operations to replace them.

Example: say there are 2 odd frequencies (a->3, b->9). Easy, just change 1. (change one a to b, OR change 1 b to an a)

Say there are 3 odd frequencies (a->3, b->9, c->5). This still takes just 1. (ex. change one a to b. KEEP THE c as is, just use it as the middle)

So it's basically just num_odd_freq // 2 is the number of moves required!

Open practice view →Open original problem ↗

05 / 05

Summary

Key Palindrome Properties:
1. s == s[::-1]
2. At most one character can have odd frequency count
3. Recursive structure: s is palindrome if s[0] == s[-1] and s[1:-1] is palindrome

Key Techniques:
1. Two Pointers - Compare from both ends
2. Expand from Center - O(n²) time, O(1) space for finding all palindromes
3. DP - Cache isPalindrome(i,j) results
4. Prefix Frequency Arrays - For query problems with rearrangement

Problem Categories:
- Validation: Check if string is/can become palindrome
- Finding: Find longest palindromic substring/subsequence
- Counting: Count number of palindromic substrings
- Queries: Answer multiple palindrome-related queries

Changes vs Removals:
- Changes: Simple two pointers, each pair is independent
- Removals: Need DP because removing s[i] vs s[j] gives different results

NEXT PATTERNDivide and Conquer→