Longest Palindromic Substring in DSA Typescript - Deep Dive

Overview - Longest Palindromic Substring

What is it?

The Longest Palindromic Substring problem asks us to find the longest continuous part of a string that reads the same forwards and backwards. A palindrome is a word or phrase that is symmetrical, like 'racecar' or 'level'. This problem helps us understand how to efficiently check and expand around centers in strings.

Why it matters

Without this concept, searching for symmetrical patterns in text would be slow and inefficient, especially for large strings. Palindromes appear in many areas like DNA sequences, text processing, and error detection. Knowing how to find the longest palindrome quickly can improve software that deals with pattern recognition and data analysis.

Where it fits

Before learning this, you should understand basic string operations and loops. After this, you can explore more complex string algorithms like Manacher's algorithm or dynamic programming for substring problems.

Mental Model

Core Idea

The longest palindromic substring is found by expanding around each character (and between characters) to check for symmetry.

Think of it like...

Imagine you have a mirror placed at different points in a word. By looking at the reflection on both sides, you find the largest symmetrical pattern centered at that mirror.

String:  a  b  a  c  d  c  a  b  a
Index:   0  1  2  3  4  5  6  7  8
Centers to check:
  - Single chars: positions 0 to 8
  - Between chars: positions between indices (0.5, 1.5, ... 7.5)
Expand left and right from each center to find palindromes.

Build-Up - 6 Steps

1

Foundation

Understanding Palindromes

Concept: What is a palindrome and how to check if a string is one.

A palindrome reads the same forwards and backwards. For example, 'madam' is a palindrome because reversing it gives 'madam'. To check if a string is a palindrome, compare characters from the start and end moving towards the center.

Result

'madam' is palindrome, 'hello' is not.

Understanding the basic property of palindromes is essential before searching for the longest one.

2

Foundation

Brute Force Search for Palindromes

Concept: Check all substrings to find the longest palindrome.

Try every possible substring of the input string. For each substring, check if it is a palindrome by comparing characters from both ends. Keep track of the longest palindrome found.

Result

For 'babad', substrings 'bab' and 'aba' are palindromes of length 3, the longest found.

Brute force works but is slow (O(n^3)) because it checks all substrings and each palindrome check takes O(n).

3

Intermediate

Expand Around Center Technique

🤔Before reading on: Do you think palindromes can only have odd lengths? Commit to your answer.

Concept: Palindromes can be centered at a single character or between two characters, allowing detection of odd and even length palindromes.

For each index in the string, treat it as the center and expand outwards while characters on both sides match. Also, consider centers between characters for even length palindromes. Keep track of the longest palindrome found during expansions.

Result

For 'cbbd', expanding around center between 'b' and 'b' finds 'bb' as longest palindrome.

Expanding around centers reduces complexity to O(n^2) and handles both odd and even length palindromes efficiently.

4

Intermediate

Implementing Center Expansion in Code

🤔Before reading on: Will expanding around every center always find the longest palindrome? Commit to yes or no.

Concept: Translate the center expansion idea into a function that expands and returns palindrome length and start index.

Write a helper function expandAroundCenter(s, left, right) that expands while s[left] == s[right]. For each index i, call expandAroundCenter(s, i, i) and expandAroundCenter(s, i, i + 1). Update max length and start position accordingly.

Result

For input 'forgeeksskeegfor', the longest palindrome found is 'geeksskeeg' starting at index 3.

Breaking the problem into a reusable expansion function simplifies the main logic and improves code clarity.

5

Advanced

Optimizing with Early Stopping

🤔Before reading on: Can we stop checking centers early if remaining string is too short? Commit to yes or no.

Concept: If the remaining characters to check are fewer than the current longest palindrome length, we can stop early to save time.

While iterating centers, if the maximum possible palindrome length from current center is less than or equal to the longest found, break the loop early.

Result

This optimization can reduce unnecessary checks, speeding up the algorithm on large strings.

Knowing when to stop searching prevents wasted work and improves performance in practice.

6

Expert

Manacher's Algorithm Overview

🤔Before reading on: Do you think it's possible to find the longest palindrome in linear time? Commit to yes or no.

Concept: Manacher's algorithm finds the longest palindromic substring in O(n) time using clever symmetry and pre-processing.

Manacher's algorithm transforms the string to handle even length palindromes uniformly, then uses a center and right boundary to reuse palindrome information. It avoids redundant expansions by mirroring palindrome lengths around centers.

Result

Manacher's algorithm returns the longest palindrome substring in linear time, much faster than center expansion for very large strings.

Understanding Manacher's algorithm reveals deep symmetry properties in palindromes and advanced optimization techniques.

Under the Hood

The center expansion method works by checking characters symmetrically around a center index or pair of indices. It compares characters moving outward until a mismatch or string boundary is reached. This exploits the palindrome property that the substring mirrors around its center. Manacher's algorithm further optimizes by storing palindrome lengths and using previously computed results to skip redundant checks.

Why designed this way?

The problem requires checking many substrings, which is expensive. Expanding around centers reduces redundant checks by focusing only on potential palindrome centers. Manacher's algorithm was designed to achieve linear time by leveraging palindrome symmetry and avoiding repeated expansions, a breakthrough over naive methods.

Input String:  a  b  a  c  d  c  a  b  a
Centers:       ^  ^  ^  ^  ^  ^  ^  ^  ^
Expand left and right:
  For center at index 2 (a):
    Compare s[1] and s[3] -> b vs c (stop)
    Palindrome: 'a'
  For center between 2 and 3:
    Compare s[2] and s[3] -> a vs c (stop)
    Palindrome: ''
  For center at index 4 (d):
    Compare s[3] and s[5] -> c vs c (expand)
    Compare s[2] and s[6] -> a vs a (expand)
    Compare s[1] and s[7] -> b vs b (expand)
    Compare s[0] and s[8] -> a vs a (expand)
    Palindrome: 'abacdcaba' (length 9)

Myth Busters - 4 Common Misconceptions

Quick: Is the longest palindromic substring always unique? Commit yes or no.

Common Belief: There is always only one longest palindromic substring in a string.

Reality: There can be multiple longest palindromic substrings of the same maximum length.

Why it matters: Assuming uniqueness can cause bugs when returning or printing results, missing other valid answers.

Quick: Does checking only odd length palindromes find all longest palindromes? Commit yes or no.

Common Belief: Checking palindromes centered only at single characters is enough.

Reality: Even length palindromes require checking centers between characters as well.

Why it matters: Ignoring even length centers misses palindromes like 'abba', leading to incorrect results.

Quick: Is Manacher's algorithm easy to implement correctly on first try? Commit yes or no.

Common Belief: Manacher's algorithm is straightforward and simple to code.

Reality: Manacher's algorithm is complex and subtle, often requiring careful debugging and understanding.

Why it matters: Underestimating its complexity can lead to wasted time and frustration in production.

Quick: Does the brute force method run fast enough for very long strings? Commit yes or no.

Common Belief: Brute force palindrome checking is efficient for all input sizes.

Reality: Brute force is very slow (O(n^3)) and impractical for large strings.

Why it matters: Using brute force in production causes performance bottlenecks and poor user experience.

Expert Zone

1

The center expansion method's performance depends heavily on input string structure; strings with many palindromes cause more expansions.

2

Manacher's algorithm uses a transformed string with inserted delimiters to unify odd and even palindrome handling, a subtle but powerful trick.

3

Tracking the right boundary and center in Manacher's algorithm allows skipping redundant checks by mirroring palindrome lengths, a non-obvious optimization.

When NOT to use

For very short strings or when simplicity is preferred, center expansion is sufficient. For extremely large inputs requiring linear time, use Manacher's algorithm. If approximate or heuristic palindrome detection is acceptable, simpler methods or hashing can be alternatives.

Production Patterns

In real systems, longest palindromic substring detection is used in DNA sequence analysis, text editors for highlighting symmetrical patterns, and compression algorithms. Often, center expansion is used for moderate input sizes, while Manacher's algorithm is reserved for performance-critical applications.

Connections

Dynamic Programming

Alternative approach to solve longest palindromic substring by building solutions for smaller substrings.

Understanding dynamic programming solutions helps compare tradeoffs in time and space complexity with center expansion.

String Hashing

Another method to check palindrome substrings efficiently using hash comparisons.

Knowing hashing techniques can enable faster palindrome checks in some contexts, complementing center expansion.

Symmetry in Physics

Both palindrome detection and physical symmetry involve mirroring properties around a center.

Recognizing symmetry as a universal concept deepens understanding of palindrome algorithms and their elegance.

Common Pitfalls

#1 Ignoring even length palindromes by only expanding around single characters.

Wrong approach:

for (let i = 0; i < s.length; i++) {
expandAroundCenter(s, i, i); // only odd length
}

Correct approach:

for (let i = 0; i < s.length; i++) {
expandAroundCenter(s, i, i); // odd length
expandAroundCenter(s, i, i + 1); // even length
}

Root cause:

Misunderstanding that palindromes can have even length and need centers between characters.

#2 Checking all substrings without optimization causing slow performance.

Wrong approach:

for (let start = 0; start < s.length; start++) {
for (let end = start; end < s.length; end++) {
if (isPalindrome(s.substring(start, end + 1))) {
updateLongest();
}
}
}

Correct approach:

Use expandAroundCenter method to reduce complexity to O(n^2) instead of O(n^3).

Root cause:

Not leveraging palindrome properties to avoid redundant checks.

#3 Returning only one longest palindrome when multiple exist.

Wrong approach:

return s.substring(start, start + maxLen); // returns first found only

Correct approach:

Collect all substrings with max length and return them or clarify requirement.

Root cause:

Assuming uniqueness of longest palindrome without verifying.

Key Takeaways

A palindrome reads the same forwards and backwards and can be odd or even length.

Expanding around centers is an efficient way to find the longest palindromic substring in O(n^2) time.

Checking centers between characters is necessary to find even length palindromes.

Manacher's algorithm can find the longest palindrome in linear time but is more complex to implement.

Understanding palindrome symmetry and expansion techniques is key to solving related string problems efficiently.

Practice

1. What is the main goal of the Longest Palindromic Substring problem?

easy

A. Find the longest substring with all unique characters

B. Find the longest substring that reads the same forwards and backwards

C. Find the longest substring with increasing characters

D. Find the longest substring that contains only vowels

Solution

1. Step 1: Understand palindrome definition

   A palindrome reads the same forwards and backwards, like 'madam' or 'racecar'.

2. Step 2: Identify the problem goal

   The problem asks to find the longest substring inside a string that is a palindrome.

3. Final Answer:

   Find the longest substring that reads the same forwards and backwards -> Option B

4. Quick Check:

   Palindrome substring = longest palindrome [OK]

Hint: Look for substrings that mirror around a center [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Looking for longest substring without repeats
• Thinking about substrings with vowels only

2. Which of the following TypeScript function signatures correctly represents a function to find the longest palindromic substring?

easy

A. function longestPalindrome(s: string): string

B. function longestPalindrome(s: number): number

C. function longestPalindrome(s: string): number[]

D. function longestPalindrome(s: boolean): string

Solution

1. Step 1: Check input parameter type

   The input is a string, so parameter type must be string.

2. Step 2: Check return type

   The function returns the longest palindromic substring, which is a string.

3. Final Answer:

   function longestPalindrome(s: string): string -> Option A

4. Quick Check:

   Input string, output string [OK]

Hint: Input and output are both strings for this problem [OK]

Common Mistakes:

• Using wrong input type like number or boolean
• Returning array instead of string
• Mixing input and output types

3. What will be the output of the following TypeScript code?

function longestPalindrome(s: string): string {
  let start = 0, maxLength = 1;
  for (let i = 0; i < s.length; i++) {
    let low = i, high = i;
    while (low >= 0 && high < s.length && s[low] === s[high]) {
      if (high - low + 1 > maxLength) {
        start = low;
        maxLength = high - low + 1;
      }
      low--;
      high++;
    }
  }
  return s.substring(start, start + maxLength);
}

console.log(longestPalindrome('babad'))

medium

A. "bab"

B. "aba"

C. "bad"

D. "babad"

Solution

1. Step 1: Understand the code logic

   The code expands around each character to find odd-length palindromes and tracks the longest one.

2. Step 2: Trace the input 'babad'

   Expanding around index 1 ('a') finds 'bab' (length 3). Around index 2 ('b') finds 'aba' (length 3). Both have length 3, but 'bab' is found first and stored.

3. Final Answer:

   "bab" -> Option A

4. Quick Check:

   First longest palindrome found = "bab" [OK]

Hint: Expand around center and pick first longest palindrome [OK]

Common Mistakes:

• Assuming 'aba' is always returned instead of 'bab'
• Returning entire string incorrectly
• Confusing substring indices

4. Identify the bug in the following TypeScript code for finding the longest palindromic substring:

function longestPalindrome(s: string): string {
  let start = 0, maxLength = 1;
  for (let i = 0; i < s.length; i++) {
    let low = i, high = i + 1;
    while (low >= 0 && high < s.length && s[low] === s[high]) {
      if (high - low + 1 > maxLength) {
        start = low;
        maxLength = high - low + 1;
      }
      low--;
      high++;
    }
  }
  return s.substring(start, start + maxLength);
}

medium

A. The loop should start from 1 instead of 0

B. The substring indices are incorrect in the return statement

C. The code only checks even-length palindromes, missing odd-length ones

D. The variables low and high are initialized incorrectly for odd-length palindromes

Solution

1. Step 1: Analyze initialization of low and high

   low = i and high = i + 1 means it only checks even-length palindromes centered between i and i+1.

2. Step 2: Identify missing odd-length palindrome check

   Odd-length palindromes centered at i (low = high = i) are not checked, so some palindromes are missed.

3. Final Answer:

   The code only checks even-length palindromes, missing odd-length ones -> Option C

4. Quick Check:

   Only even-length palindrome check = bug [OK]

Hint: Check both odd (low=high=i) and even (low=i, high=i+1) centers [OK]

Common Mistakes:

• Checking only even-length palindromes
• Not expanding around single character centers
• Incorrect loop start index

5. Given the string "forgeeksskeegfor", which approach correctly finds the longest palindromic substring and what is that substring?

hard

A. Manacher's algorithm; longest palindrome is "forgeeksskeegfor"

B. Dynamic programming approach; longest palindrome is "forgeeksskeegfor"

C. Brute force checking all substrings; longest palindrome is "ss"

D. Expand around center approach; longest palindrome is "geeksskeeg"

Solution

1. Step 1: Identify the longest palindrome in the string

   The substring "geeksskeeg" is the longest palindrome inside "forgeeksskeegfor".

2. Step 2: Match approach with correct palindrome

   Expand around center approach finds "geeksskeeg" correctly. The entire string is not a palindrome, so options A and B are incorrect. Brute force (C) incorrectly identifies "ss" as the longest.

3. Final Answer:

   Expand around center approach; longest palindrome is "geeksskeeg" -> Option D

4. Quick Check:

   Center expansion finds "geeksskeeg" [OK]

Hint: Use center expansion for efficient palindrome search [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Confusing brute force with efficient methods
• Mixing up palindrome substrings