Longest Palindromic Substring in DSA Typescript

Mental Model

Find the longest part of a string that reads the same forwards and backwards by checking around each character.

Analogy: Imagine looking for the biggest mirror in a hallway where the reflection looks exactly the same from both sides, starting from each spot and expanding outwards.

s = "b a b a d"
indexes: 0 1 2 3 4
Check centers like:
  ↑
 b a b a d
Then expand left and right pointers to find palindromes.

Dry Run Walkthrough

Input: string: "babad"

Goal: Find the longest substring that reads the same forwards and backwards

Step 1: Start at index 0, check odd length palindrome centered at 'b'

"b" (index 0) is palindrome

Why: Single character is always palindrome

Step 2: Expand around center 0 for odd length: compare characters at -1 and 1 (out of bounds and 'a')

"b" remains longest palindrome

Why: Left pointer out of bounds, stop expanding

Step 3: Check even length palindrome centered between index 0 and 1 ('b' and 'a')

No palindrome longer than 1 found

Why: Characters differ, no even palindrome here

Step 4: Move to index 1, check odd length palindrome centered at 'a'

"a" is palindrome

Why: Single character palindrome

Step 5: Expand around center 1: compare characters at 0 and 2 ('b' and 'b')

"bab" palindrome found

Why: Characters match, palindrome expands

Step 6: Expand further: compare characters at -1 and 3 (out of bounds and 'a')

"bab" remains longest palindrome

Why: Left pointer out of bounds, stop expanding

Step 7: Check even length palindrome centered between index 1 and 2 ('a' and 'b')

No longer palindrome found

Why: Characters differ

Step 8: Move to index 2, check odd length palindrome centered at 'b'

"b" palindrome

Why: Single character palindrome

Step 9: Expand around center 2: compare characters at 1 and 3 ('a' and 'a')

"aba" palindrome found

Why: Characters match, palindrome expands

Step 10: Expand further: compare characters at 0 and 4 ('b' and 'd')

"aba" remains longest palindrome

Why: Characters differ, stop expanding

Result:

"bab" or "aba" are longest palindromic substrings

Annotated Code

DSA Typescript

class Solution {
  longestPalindrome(s: string): string {
    if (s.length < 1) return "";
    let start = 0, end = 0;

    const expandAroundCenter = (left: number, right: number): number => {
      while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
      }
      return right - left - 1; // length of palindrome
    };

    for (let i = 0; i < s.length; i++) {
      const len1 = expandAroundCenter(i, i); // odd length
      const len2 = expandAroundCenter(i, i + 1); // even length
      const len = Math.max(len1, len2);
      if (len > end - start) {
        start = i - Math.floor((len - 1) / 2);
        end = i + Math.floor(len / 2);
      }
    }

    return s.substring(start, end + 1);
  }
}

// Driver code
const sol = new Solution();
console.log(sol.longestPalindrome("babad"));

while (left >= 0 && right < s.length && s[left] === s[right]) {

expand pointers outward while characters match to find palindrome length

return right - left - 1;

calculate length of palindrome found

const len1 = expandAroundCenter(i, i);

check odd length palindrome centered at i

const len2 = expandAroundCenter(i, i + 1);

check even length palindrome centered between i and i+1

if (len > end - start) {

update longest palindrome boundaries if longer palindrome found

start = i - Math.floor((len - 1) / 2);

calculate new start index of palindrome

end = i + Math.floor(len / 2);

calculate new end index of palindrome

Output

bab

Complexity Analysis

Time: O(n^2) because for each character we expand outwards checking palindrome substrings

Space: O(1) because we only store indices and no extra data structures proportional to input size

vs Alternative: Compared to dynamic programming O(n^2) time and O(n^2) space, this approach uses less space and is simpler

Edge Cases

empty string

returns empty string immediately

DSA Typescript

if (s.length < 1) return "";

string with all same characters, e.g. "aaaa"

returns the entire string as palindrome

DSA Typescript

while (left >= 0 && right < s.length && s[left] === s[right]) {

string with no palindrome longer than 1, e.g. "abc"

returns any single character as palindrome

DSA Typescript

const len1 = expandAroundCenter(i, i);

When to Use This Pattern

When asked to find the longest substring that reads the same forwards and backwards, use the expand around center pattern to efficiently check palindromes from each position.

Common Mistakes

Mistake: Only checking odd length palindromes and missing even length ones
Fix: Check both odd and even length palindromes by expanding around one center and two centers

Mistake: Not updating start and end indices correctly after finding a longer palindrome
Fix: Calculate start and end using the palindrome length and center index carefully

Summary

Finds the longest substring that reads the same forwards and backwards by expanding around each character.

Use when you need to find the longest palindromic substring efficiently without extra space.

The key insight is to expand around centers to check palindromes of both odd and even lengths.

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