Longest Palindromic Substring in DSA Typescript - Execution Trace

Concept Flow - Longest Palindromic Substring

left

↓

b

↓

0

↓

a

↓

1

↓

0

The Expand Around Center approach checks every possible palindrome center. For a string of length n there are 2n-1 centers: n single characters (odd-length palindromes) and n-1 gaps between characters (even-length palindromes). For each center, expand outward while characters match, tracking the longest palindrome found.

Execution Sample

DSA Typescript

function longestPalindrome(s: string): string {
    let start = 0, maxLen = 1;

    function expand(left: number, right: number): void {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            if (right - left + 1 > maxLen) {
                maxLen = right - left + 1;
                start = left;
            }
            left--;
            right++;
        }
    }

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

    return s.substring(start, start + maxLen);
}

Trace on s='babad': i=0: expand(0,0)='b' len=1. expand(0,1): s[0]='b'≠s[1]='a', stop. i=1: expand(1,1): s[0]=s[2]='b' → 'bab' len=3, start=0. expand more: out of bounds. expand(1,2): s[1]='a'≠s[2]='b', stop. i=2: expand(2,2): s[1]=s[3]='a' → 'aba' len=3 (not > 3, no update). expand(2,2) more: s[0]='b'≠s[4]='d', stop. expand(2,3): s[2]='b'≠s[3]='a', stop. i=3,4: no longer palindromes found. Return s.substring(0,3)='bab'.

Execution Table

i	type	left,right	match?	palindrome	maxLen	start
0	odd	0,0	init	b	1	0
0	even	0,1	b≠a	stop	1	0
1	odd	1,1	init	a	1	0
1	odd	0,2	b=b ✓	bab	3	0
1	odd	-1,3	OOB	stop	3	0
1	even	1,2	a≠b	stop	3	0
2	odd	2,2	init	b	1→3 tie	0
2	odd	1,3	a=a ✓	aba	3 (no update)	0
2	odd	0,4	b≠d	stop	3	0
2	even	2,3	b≠a	stop	3	0
3	odd	3,3	init	a	1→3 tie	0
3	odd	2,4	b≠d	stop	3	0
3	even	3,4	a≠d	stop	3	0
4	odd	4,4	init	d	1→3 tie	0
4	even	4,5	OOB	stop	3	0

💡 Final: start=0, maxLen=3. Return s.substring(0,3) = 'bab'. Both 'bab' and 'aba' are valid answers for 'babad'.

Variable Tracker

step	i	action	start	maxLen	result so far
init	-	initialize	0	1	b
i=0 odd	0	expand(0,0): 'b' only	0	1	b
i=0 even	0	expand(0,1): mismatch	0	1	b
i=1 odd	1	expand(1,1)→(0,2): 'bab'	0	3	bab
i=1 even	1	expand(1,2): mismatch	0	3	bab
i=2 odd	2	expand(2,2)→(1,3): 'aba' tie	0	3	bab
i=2 even	2	expand(2,3): mismatch	0	3	bab
i=3,4	3,4	no improvement	0	3	bab
done	-	return substring(0,3)	0	3	bab

Key Moments - 3 Insights

Why do we need both odd and even center expansions?

Odd-length palindromes (like 'aba') have a single center character. Even-length palindromes (like 'abba') have a center between two characters. Calling expand(i,i) handles odd; expand(i,i+1) handles even. Missing even expansions would fail to find palindromes like 'abba' or 'cbbd' → 'bb'.

Why is TypeScript's Infinity safe to use for initialization in this problem?

This specific problem doesn't use Infinity — but for related DP palindrome problems (like Palindrome Partitioning II), TypeScript's Infinity works correctly with Math.min() because Infinity + 1 = Infinity and Math.min(Infinity, x) = x for any finite x.

What is the time and space complexity of the expand-around-center approach?

Time O(n²): 2n-1 centers × O(n) expansion each. Space O(1): only track start index and maxLen — no extra array. This is optimal for a non-DP approach. Manacher's algorithm achieves O(n) but is significantly harder to implement.

Visual Quiz - 3 Questions

For s='cbbd', what is the longest palindromic substring?

A "cbbd"

B "bb"

C "c"

D "cbd"

💡 Hint

Check even-length expansion at center between index 1 and 2: s[1]='b'=s[2]='b' → 'bb'.

How many centers does the expand-around-center algorithm check for a string of length n?

A n

B n + 1

C 2n - 1

D n²

💡 Hint

n single-character centers (odd) + n-1 gap centers (even) = 2n-1.

What does s.substring(start, start + maxLen) return when start=0 and maxLen=3 for s='babad'?

A "bab"

B "aba"

C "bad"

D "babad"

💡 Hint

substring(0, 3) extracts characters at indices 0,1,2 = 'b','a','b' = 'bab'.

Concept Snapshot

Longest Palindromic Substring = expand around center. For each of 2n-1 centers: expand while s[left]===s[right], track max length. Two calls per index: expand(i,i) for odd, expand(i,i+1) for even. TypeScript: use s.substring(start, start+maxLen) to extract. Time O(n²), Space O(1).

Full Transcript

Let's find the longest palindromic substring of 'babad' using expand-around-center. We have n=5 characters, so 2×5-1=9 centers to check. i=0: Odd expansion at 'b': just 'b', length 1. Even expansion between 'b' and 'a': mismatch immediately. i=1: Odd expansion at 'a': check left=0,right=2: s[0]='b'=s[2]='b' — match! Palindrome 'bab', length 3. Update maxLen=3, start=0. Continue: left=-1, out of bounds, stop. Even expansion between 'a' and 'b': mismatch. i=2: Odd expansion at 'b': check left=1,right=3: s[1]='a'=s[3]='a' — match! Palindrome 'aba', length 3. Not greater than current maxLen, so no update. Continue: left=0,right=4: s[0]='b'≠s[4]='d', stop. Even expansion between 'b' and 'a': mismatch. i=3,4: No palindromes longer than 3 found. Final: start=0, maxLen=3. Return s.substring(0,3) = 'bab'. Key TypeScript note: use s.substring(start, start+maxLen) not s.slice(start, start+maxLen) — both work here but substring handles negative arguments differently.

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