Longest Palindromic Substring in DSA C++

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 ends.

s = "b a b a d"
indexes: 0 1 2 3 4
Check centers like:
  b (0) ↑
  a (1) ↑
  b (2) ↑
  a (3) ↑
  d (4) ↑

Dry Run Walkthrough

Input: string: "babad"

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

Step 1: Check odd-length palindrome centered at index 0 ('b')

"b" -> palindrome found: "b"

Why: Start by checking single character center for palindromes

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

No palindrome longer than 1 found here

Why: Check even length palindromes between characters

Step 3: Check odd-length palindrome centered at index 1 ('a')

"bab" palindrome found expanding from index 1

Why: Expand around center to find palindrome "bab"

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

No palindrome longer than 3 found here

Why: No even length palindrome here

Step 5: Check odd-length palindrome centered at index 2 ('b')

"aba" palindrome found expanding from index 2

Why: Found another palindrome "aba" of length 3

Step 6: Check odd-length palindrome centered at index 3 ('a')

"a" palindrome found

Why: Single character palindrome

Step 7: Check odd-length palindrome centered at index 4 ('d')

"d" palindrome found

Why: Single character palindrome

Result:

"bab" or "aba" are the longest palindromic substrings

Annotated Code

DSA C++

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int start = 0, maxLen = 1;

        // Helper lambda to expand around center
        auto expandAroundCenter = [&](int left, int right) {
            while (left >= 0 && right < (int)s.size() && s[left] == s[right]) {
                left--;
                right++;
            }
            return right - left - 1; // length of palindrome
        };

        for (int i = 0; i < (int)s.size(); i++) {
            int len1 = expandAroundCenter(i, i);       // odd length
            int len2 = expandAroundCenter(i, i + 1);   // even length
            int len = max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        return s.substr(start, maxLen);
    }
};

int main() {
    Solution sol;
    string input = "babad";
    cout << sol.longestPalindrome(input) << endl;
    return 0;
}

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

expand palindrome boundaries while characters match

left--; right++;

move pointers outward to check larger palindrome

int len1 = expandAroundCenter(i, i);

check odd length palindrome centered at i

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

check even length palindrome centered between i and i+1

if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; }

update longest palindrome start and length if found longer

Output

bab

Complexity Analysis

Time: O(n^2) because for each character we expand around center which can take up to O(n) steps

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

vs Alternative: Compared to checking all substrings (O(n^3)), expanding around center is faster and simpler

Edge Cases

empty string

returns empty string immediately

DSA C++

if (s.empty()) return "";

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

returns the entire string as palindrome

DSA C++

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

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

returns any single character as palindrome

DSA C++

int maxLen = 1;

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 check palindromes efficiently.

Common Mistakes

Mistake: Only checking odd length palindromes and missing even length ones
Fix: Check both odd and even length palindromes by expanding around single character and between two characters

Mistake: Not updating start index correctly when a longer palindrome is found
Fix: Calculate start as i - (len - 1) / 2 to get correct starting index

Summary

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

Use when you need to find the longest palindromic substring efficiently without checking all substrings.

The key insight is to expand around each character (and between characters) to find palindromes in O(n^2) time.

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