Longest Palindromic Substring in DSA Javascript - Execution Trace

Concept Flow - Longest Palindromic Substring

Start with each index i in string

↓

Expand around center i (odd length)

↓

Expand around center i and i+1 (even length)

↓

Check palindrome length

↓

Update longest palindrome if longer

↓

Repeat for all i

↓

Return longest palindrome substring

We check every character and pair as center, expand outwards to find palindromes, and keep track of the longest one.

Execution Sample

DSA Javascript

function longestPalindrome(s) {
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    let len1 = expand(s, i, i);
    let len2 = expand(s, i, i + 1);
    let len = Math.max(len1, len2);
    if (len > end - start + 1) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.substring(start, end + 1);
}

function expand(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  return right - left - 1;
}

This code finds the longest palindromic substring by expanding around each center and updating the longest found.

Execution Table

Step	Operation	Center Indices	Palindrome Length Found	Longest Palindrome Indices	Visual State
1	Expand odd center	i=0, i=0	1	start=0, end=0	"a"
2	Expand even center	i=0, i+1=1	0	start=0, end=0	"a"
3	Update longest	len=1	1	start=0, end=0	"a"
4	Expand odd center	i=1, i=1	3	start=0, end=0	"a"
5	Expand even center	i=1, i+1=2	0	start=0, end=0	"a"
6	Update longest	len=3	3	start=0, end=2	"aba"
7	Expand odd center	i=2, i=2	1	start=0, end=2	"aba"
8	Expand even center	i=2, i+1=3	0	start=0, end=2	"aba"
9	Update longest	len=1	1	start=0, end=2	"aba"
10	Expand odd center	i=3, i=3	1	start=0, end=2	"aba"
11	Expand even center	i=3, i+1=4	0	start=0, end=2	"aba"
12	Update longest	len=1	1	start=0, end=2	"aba"
13	Expand odd center	i=4, i=4	1	start=0, end=2	"aba"
14	Expand even center	i=4, i+1=5	0	start=0, end=2	"aba"
15	Update longest	len=1	1	start=0, end=2	"aba"
16	End loop	i=5 (end)	-	start=0, end=2	"aba"

💡 Loop ends after checking all centers; longest palindrome is from index 0 to 2.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	Final
start	0	0	0	0	0	0	0
end	0	0	2	2	2	2	2
i	0	1	2	3	4	5	5
len	-	1	3	1	1	1	-

Key Moments - 3 Insights

Why do we check two centers (i,i) and (i,i+1)?

Because palindromes can be odd length (center at one character) or even length (center between two characters). See steps 1-2 and 4-5 in execution_table.

Why do we subtract 1 in 'right - left - 1' when calculating palindrome length?

Because after the while loop breaks, left and right are one step beyond the palindrome bounds. So length is right - left - 1. This is shown in the expand function in the code.

How do we update start and end indices for the longest palindrome?

We calculate start as i - floor((len-1)/2) and end as i + floor(len/2) to cover both odd and even length palindromes. This update happens in steps 3 and 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what palindrome length was found expanding around center (1,2)?

A 3

B 1

C 0

D 2

💡 Hint

Check the 'Palindrome Length Found' column at step 5 in execution_table.

At which step does the longest palindrome update to length 3?

A Step 3

B Step 6

C Step 9

D Step 12

💡 Hint

Look for 'Update longest' operation with length 3 in execution_table.

If the input string was 'aaaa', how would the longest palindrome length change at step 5?

A It would be 4

B It would be 3

C It would be 2

D It would be 1

💡 Hint

Consider expanding around centers in a string of repeated characters; check how palindrome length grows in execution_table.

Concept Snapshot

Longest Palindromic Substring:
- Check each index as center (odd length) and between indices (even length)
- Expand outwards while characters match
- Track longest palindrome start and end indices
- Return substring from start to end
- Time complexity O(n^2), space O(1)

Full Transcript

The longest palindromic substring problem finds the largest substring that reads the same forwards and backwards. We do this by checking every character and every pair of characters as centers, expanding outwards to find palindromes. We keep track of the longest palindrome found by updating start and end indices. The expansion stops when characters don't match or boundaries are reached. Finally, we return the substring from start to end. This approach runs in quadratic time and uses constant extra space.

Practice

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

easy

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

B. Find the longest substring with all unique characters

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 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 A

4. Quick Check:

   Longest Palindromic Substring = Find palindrome substring [OK]

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

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking about subsequences instead of substrings
• Ignoring the order of characters

2. Which of the following JavaScript code snippets correctly initializes a 2D array dp for dynamic programming in the Longest Palindromic Substring problem?

easy

A. const dp = Array.from({ length: n }, () => Array(n).fill(false));

B. const dp = Array(n).fill(Array(n).fill(false));

C. const dp = new Array(n).fill(new Array(n).fill(false));

D. const dp = Array(n).map(Array(n).fill(false));

Solution

1. Step 1: Understand 2D array initialization in JavaScript

   Using Array.from with a mapping function creates independent inner arrays.

2. Step 2: Analyze each option

   B and C fill with the same inner array reference, causing bugs. D uses map incorrectly by passing an array instead of a function, which won't work. A correctly creates independent arrays.

3. Final Answer:

   const dp = Array.from({ length: n }, () => Array(n).fill(false)); -> Option A

4. Quick Check:

   Correct 2D array init = const dp = Array.from({ length: n }, () => Array(n).fill(false)); [OK]

Hint: Use Array.from with arrow function for independent inner arrays [OK]

Common Mistakes:

• Using fill with object references causing shared inner arrays
• Using map on uninitialized arrays
• Not initializing inner arrays separately

3. What will be the output of the following JavaScript code snippet?

function longestPalindrome(s) {
  let maxLen = 1, start = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      let substr = s.slice(i, j + 1);
      if (substr === substr.split('').reverse().join('') && substr.length > maxLen) {
        maxLen = substr.length;
        start = i;
      }
    }
  }
  return s.slice(start, start + maxLen);
}
console.log(longestPalindrome('babad'));

medium

A. "aba"

B. "babad"

C. "bad"

D. "bab"

Solution

1. Step 1: Understand the nested loops and palindrome check

   The code checks all substrings and updates the longest palindrome found.

2. Step 2: Trace substrings in 'babad'

   Palindromes found include 'bab' and 'aba', both length 3. The code updates maxLen and start when it finds 'aba' last (i=1,j=3), because the condition uses >, so it updates only if strictly longer. 'bab' is found first but 'aba' is found later and has the same length, so it is not updated. Actually, the code updates only if substr.length > maxLen, so the first palindrome of length 3 is 'bab' (i=0,j=2), maxLen becomes 3. Then 'aba' (i=1,j=3) is also length 3, so substr.length > maxLen is false (3 > 3 is false), so maxLen and start are not updated. Therefore, the returned palindrome is 'bab'.

3. Final Answer:

   "bab" -> Option D

4. Quick Check:

   First longest palindrome found = "bab" [OK]

Hint: Check all substrings; first longest palindrome returned [OK]

Common Mistakes:

• Assuming 'aba' is returned instead of 'bab'
• Confusing substring with subsequence
• Ignoring order of substring checks

4. The following code attempts to find the longest palindromic substring but has a bug. What is the bug?

function longestPalindrome(s) {
  let maxLen = 1, start = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      let substr = s.slice(i, j + 1);
      if (substr === substr.split('').reverse().join('') && substr.length >= maxLen) {
        maxLen = substr.length;
        start = i;
      }
    }
  }
  return s.slice(start, start + maxLen);
}
console.log(longestPalindrome('cbbd'));

medium

A. The reverse method does not work on strings

B. The slice method is used incorrectly

C. Using >= causes the last palindrome to be chosen instead of the first

D. The loop ranges are off by one

Solution

1. Step 1: Analyze the condition with >=

   The condition uses >=, so if two palindromes have the same length, the later one overwrites the earlier.

2. Step 2: Understand effect on output

   For input 'cbbd', palindromes 'bb' and 'b' exist. Using >= picks the last palindrome of max length, which may not be desired.

3. Final Answer:

   Using >= causes the last palindrome to be chosen instead of the first -> Option C

4. Quick Check:

   Condition >= picks last palindrome [OK]

Hint: Use > to pick first longest palindrome found [OK]

Common Mistakes:

• Thinking slice is incorrect
• Believing reverse doesn't work on strings
• Ignoring >= vs > difference

5. Given the string s = 'forgeeksskeegfor', which approach below efficiently finds the longest palindromic substring and what is that substring?

hard

A. Expand around center approach; longest palindrome is 'eeksskee'

B. Dynamic programming with 2D table; longest palindrome is 'geeksskeeg'

C. Sorting characters and checking; longest palindrome is 'ss'

D. Brute force checking all substrings; longest palindrome is 'forgeeksskeegfor'

Solution

1. Step 1: Understand problem and input

   The string 'forgeeksskeegfor' contains a long palindrome 'geeksskeeg'.

2. Step 2: Evaluate approaches

   Brute force checking all substrings is inefficient and won't find the full string palindrome. Sorting characters loses order, so 'ss' is incorrect. Dynamic programming with 2D table finds 'geeksskeeg' correctly, unlike other options.

3. Final Answer:

   Dynamic programming with 2D table; longest palindrome is 'geeksskeeg' -> Option B

4. Quick Check:

   DP approach finds 'geeksskeeg' efficiently [OK]

Hint: Use DP table to track palindromes efficiently [OK]

Common Mistakes:

• Assuming whole string is palindrome
• Using sorting which breaks character order
• Confusing expand around center with brute force