Longest Palindromic Substring in DSA C++ - Execution Trace

Concept Flow - Longest Palindromic Substring

Start

↓

Pick center index i

↓

Expand around i for odd length palindrome

↓

Expand around i and i+1 for even length palindrome

↓

Update longest palindrome if found longer

↓

Move to next center index

↓

Repeat until all centers checked

↓

Return longest palindrome substring

We check each index as a center and expand outwards to find palindromes, updating the longest found.

Execution Sample

DSA C++

void expandAroundCenter(const string& s, int left, int right, int& start, int& maxLen) {
  while (left >= 0 && right < s.size() && s[left] == s[right]) {
    left--;
    right++;
  }
  int len = right - left - 1;
  if (len > maxLen) {
    start = left + 1;
    maxLen = len;
  }
}

string longestPalindrome(string s) {
  int start = 0, maxLen = 1;
  for (int i = 0; i < s.size(); i++) {
    expandAroundCenter(s, i, i, start, maxLen);
    expandAroundCenter(s, i, i + 1, start, maxLen);
  }
  return s.substr(start, maxLen);
}

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

Execution Table

Step	Operation	Center Indices	Palindrome Found	Longest Palindrome (start, length)	Visual State
1	Pick center	i=0	"a"	(0,1)	"a"
2	Expand odd	left=0, right=0	"a"	(0,1)	"a"
3	Expand even	left=0, right=1	""	(0,1)	"a"
4	Pick center	i=1	"b"	(0,1)	"a"
5	Expand odd	left=1, right=1	"b"	(0,1)	"a"
6	Expand even	left=1, right=2	""	(0,1)	"a"
7	Pick center	i=2	"a"	(0,1)	"a"
8	Expand odd	left=2, right=2	"aba"	(0,3)	"aba"
9	Expand even	left=2, right=3	""	(0,3)	"aba"
10	Pick center	i=3	"c"	(0,3)	"aba"
11	Expand odd	left=3, right=3	"c"	(0,3)	"aba"
12	Expand even	left=3, right=4	""	(0,3)	"aba"
13	Pick center	i=4	"a"	(0,3)	"aba"
14	Expand odd	left=4, right=4	"a"	(0,3)	"aba"
15	Expand even	left=4, right=5	""	(0,3)	"aba"
16	Pick center	i=5	"b"	(0,3)	"aba"
17	Expand odd	left=5, right=5	"bab"	(3,3)	"bab"
18	Expand even	left=5, right=6	""	(3,3)	"bab"
19	Pick center	i=6	"a"	(3,3)	"bab"
20	Expand odd	left=6, right=6	"a"	(3,3)	"bab"
21	Expand even	left=6, right=7	""	(3,3)	"bab"
22	Pick center	i=7	"d"	(3,3)	"bab"
23	Expand odd	left=7, right=7	"d"	(3,3)	"bab"
24	Expand even	left=7, right=8	""	(3,3)	"bab"
25	Pick center	i=8	"a"	(3,3)	"bab"
26	Expand odd	left=8, right=8	"a"	(3,3)	"bab"
27	Expand even	left=8, right=9	""	(3,3)	"bab"
28	End			(3,3)	"bab"

💡 All centers checked, longest palindrome found at start=3 with length=3

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	Final
start	0	0	0	0	0	0	0	0	3	3
maxLen	1	1	1	1	1	1	1	3	3	3
i	0	1	2	3	4	5	6	7	8	9

Key Moments - 3 Insights

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

Because palindromes can be odd length (centered at one character) or even length (centered between two characters). See execution_table rows 2-3 and 5-6 for examples.

How do we update the longest palindrome when expanding?

When the expanded substring length is longer than maxLen, we update start and maxLen. See execution_table row 8 where palindrome "aba" updates longest.

Why does the expansion stop when characters don't match?

Because palindrome property breaks if characters at left and right differ. Expansion stops and we record the last valid palindrome. See rows 3, 6, 9 where expansions end.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the palindrome found?

A "aba"

B "bab"

C "a"

D "c"

💡 Hint

Check the 'Palindrome Found' column at step 8 in execution_table.

At which step does the longest palindrome update to "bab"?

A Step 17

B Step 8

C Step 5

D Step 3

💡 Hint

Look for the 'Longest Palindrome' column where start changes to 3 and length to 3.

If we skip checking even length centers (i, i+1), what palindrome would we miss?

A "aba"

B "bab"

C " (empty string)

D "a"

💡 Hint

Check expansions around even centers in execution_table rows 6 and 18.

Concept Snapshot

Longest Palindromic Substring:
- Check each index as center
- Expand around center for odd and even length
- Update longest when longer palindrome found
- Return substring from start with max length
- Time complexity O(n^2), space O(1)

Full Transcript

The Longest Palindromic Substring problem finds the longest substring that reads the same forwards and backwards. The approach is to treat each character index as a center and expand outwards to check for palindromes. We do this twice for each center: once for odd length palindromes (centered at one character) and once for even length palindromes (centered between two characters). We keep track of the longest palindrome found by updating the start index and maximum length. The expansion stops when characters at left and right pointers differ. After checking all centers, we return the longest palindrome substring. This method runs in O(n^2) time and uses O(1) 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 the problem statement

   The problem asks to find the longest part of a string that is a palindrome, meaning it reads the same forwards and backwards.

2. Step 2: Compare options with the problem goal

   Only Find the longest substring that reads the same forwards and backwards describes finding a substring that reads the same forwards and backwards, which matches the palindrome definition.

3. Final Answer:

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

4. Quick Check:

   Longest Palindromic Substring = Find the longest substring that reads the same forwards and backwards [OK]

Hint: Look for substring that reads same forwards and backwards [OK]

Common Mistakes:

• Confusing palindrome with unique characters
• Thinking about substrings with vowels only
• Mixing substring with subsequence

2. Which of the following C++ code snippets correctly initializes a 2D vector dp of size n x n with false values for the Longest Palindromic Substring problem?

easy

A. std::vector dp(n, std::vector<int>(n, false));

B. std::vector<bool> dp(n, std::vector<bool>(n, false));

C. std::vector dp(n, n, false);

D. std::vector dp(n, std::vector<bool>(n, false));

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector of booleans with size n x n, use vector of vectors: std::vector dp(n, std::vector<bool>(n, false));

2. Step 2: Check each option's correctness

   std::vector dp(n, std::vector<bool>(n, false)); uses correct syntax. std::vector<bool> dp(n, std::vector<bool>(n, false)); tries to assign vector<bool> to vector<bool>, which is invalid. std::vector dp(n, std::vector<int>(n, false)); uses int instead of bool. std::vector dp(n, n, false); uses invalid constructor syntax.

3. Final Answer:

   std::vector dp(n, std::vector<bool>(n, false)); -> Option D

4. Quick Check:

   Correct 2D vector initialization = std::vector dp(n, std::vector<bool>(n, false)); [OK]

Hint: Use vector of vectors with inner vector initialized [OK]

Common Mistakes:

• Using wrong data type for dp vector
• Incorrect constructor syntax for 2D vector
• Confusing vector<bool> with vector

3. What is the output of the following C++ code snippet that finds the longest palindromic substring length?

std::string s = "babad";
int n = s.size();
int maxLength = 1;
for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
    int left = i, right = j;
    bool isPalindrome = true;
    while (left < right) {
      if (s[left] != s[right]) {
        isPalindrome = false;
        break;
      }
      left++; right--;
    }
    if (isPalindrome && (j - i + 1) > maxLength) {
      maxLength = j - i + 1;
    }
  }
}
std::cout << maxLength << std::endl;

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Understand the code logic

   The code checks all substrings of "babad" and updates maxLength if the substring is a palindrome and longer than current maxLength.

2. Step 2: Identify longest palindromic substrings in "babad"

   "bab" and "aba" are palindromes of length 3. No longer palindrome exists.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest palindrome length in "babad" = 3 [OK]

Hint: Check all substrings and update max length if palindrome [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Counting non-palindromic substrings
• Off-by-one errors in substring length

4. Identify the bug in the following C++ code snippet intended to find the longest palindromic substring length:

std::string s = "cbbd";
int n = s.size();
int maxLength = 1;
for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
    int left = i, right = j;
    while (left < right) {
      if (s[left] != s[right]) {
        break;
      }
      left++; right--;
    }
    if ((j - i + 1) > maxLength) {
      maxLength = j - i + 1;
    }
  }
}
std::cout << maxLength << std::endl;

medium

A. Incorrect loop ranges for i and j

B. Wrong initialization of maxLength

C. Missing check if substring is palindrome before updating maxLength

D. Using break instead of continue in while loop

Solution

1. Step 1: Analyze palindrome check logic

   The code breaks out of while loop if characters don't match but does not track if substring is palindrome.

2. Step 2: Check maxLength update condition

   maxLength is updated without confirming substring is palindrome, causing incorrect results.

3. Final Answer:

   Missing check if substring is palindrome before updating maxLength -> Option C

4. Quick Check:

   Must confirm palindrome before updating maxLength [OK]

Hint: Always confirm palindrome before updating max length [OK]

Common Mistakes:

• Updating maxLength without palindrome check
• Confusing break and continue in loops
• Incorrect loop boundaries

5. Given the string "forgeeksskeegfor", which approach below efficiently finds the longest palindromic substring and what is its length?

hard

A. Dynamic Programming approach, length 7

B. Expand Around Center approach, length 10

C. Brute Force approach, length 12

D. Manacher's Algorithm, length 8

Solution

1. Step 1: Identify longest palindrome in "forgeeksskeegfor"

   The longest palindromic substring is "geeksskeeg" with length 10.

2. Step 2: Choose efficient approach

   Expand Around Center approach efficiently finds palindromes by expanding from each center, suitable for this problem.

3. Final Answer:

   Expand Around Center approach, length 10 -> Option B

4. Quick Check:

   Longest palindrome length = 10 using Expand Around Center [OK]

Hint: Expand from centers to find longest palindrome efficiently [OK]

Common Mistakes:

• Confusing length of palindrome substring
• Choosing less efficient brute force for large strings
• Mixing up algorithm names and their complexities