Longest Palindromic Substring in DSA C - Execution Trace

Concept Flow - Longest Palindromic Substring

Input: "babad"

For each center position, expand outward while chars match:

Center i=0 ('b'):  odd expand → "b"          len=1
Center i=1 ('a'):  odd expand → "bab"        len=3  ←
                   even expand→ "" (b≠a)     len=0
Center i=2 ('b'):  odd expand → "aba"        len=3  ←
                   even expand→ "" (b≠a)     len=0
Center i=3 ('a'):  odd expand → "a"          len=1
                   even expand→ "" (a≠d)     len=0
Center i=4 ('d'):  odd expand → "d"          len=1

Longest = "bab" (or "aba", first found wins)
start=0, maxLen=3 → return s[0..2] = "bab"

Expand Around Center treats every character (odd length) and every gap between characters (even length) as a potential palindrome center. Expand left and right while characters match. Track the longest expansion found. One pass, O(n²) time, O(1) space — no extra array needed.

Execution Sample

DSA C

#include <string.h>
#include <stdlib.h>

void expandCenter(const char *s, int left, int right, int n,
                  int *outStart, int *outLen) {
    while (left >= 0 && right < n && s[left] == s[right]) {
        left--;
        right++;
    }
    /* After loop: left+1..right-1 is the palindrome */
    int len = right - left - 1;
    if (len > *outLen) {
        *outLen = len;
        *outStart = left + 1;
    }
}

char *longestPalindrome(char *s) {
    int n = strlen(s);
    if (n == 0) return "";
    int start = 0, maxLen = 1;
    for (int i = 0; i < n; i++) {
        expandCenter(s, i, i,   n, &start, &maxLen); /* odd */
        expandCenter(s, i, i+1, n, &start, &maxLen); /* even */
    }
    char *result = (char *)malloc(maxLen + 1);
    strncpy(result, s + start, maxLen);
    result[maxLen] = '\0';
    return result;
}

Trace on 'babad': center i=1 ('a'), odd expansion: left=1,right=1 → left=0,right=2 (b==b, expand) → left=-1 (stop). Palindrome is s[1..1] wait — after loop left=0-1=-1, right=2+1=3, len=3-(-1)-1=3, start=0. Returns 'bab'.

Execution Table

i	type	initial L,R	expansions	final L,R	len	start	maxLen
0	odd	0,0	none (bounds)	-1,1	1	0	1
1	odd	1,1	0,2(b==b)→-1,3(stop)	-1,3	3	0	3
1	even	1,2	none (a≠b)	1,2	0	0	3
2	odd	2,2	1,3(a==a)→0,4(b==b)→-1,5(stop)	-1,5	3	0	3
2	even	2,3	none (b≠a)	2,3	0	0	3
3	odd	3,3	none (bounds tight)	2,4	1	0	3
4	odd	4,4	none (bounds)	3,5	1	0	3

💡 maxLen=3, start=0. Result = s[0..2] = "bab". Note: center i=2 also gives len=3 ("aba") but start stays 0 since 3 is not > 3.

Variable Tracker

event	i	type	left (exit)	right (exit)	len	start	maxLen
init	-	-	-	-	-	0	1
i=0 odd	0	odd	-1	1	1	0	1
i=1 odd	1	odd	-1	3	3	0	3
i=1 even	1	even	1	2	0	0	3
i=2 odd	2	odd	-1	5	3	0	3
i=2 even	2	even	2	3	0	0	3
i=3,4	3-4	-	-	-	1	0	3

Key Moments - 4 Insights

After expandCenter exits, why is the palindrome at indices left+1 to right-1, not left to right?

The while loop exits when s[left] != s[right] or bounds are hit — meaning left and right have already moved one step past the valid palindrome. The actual palindrome ends at left+1 on the left side and right-1 on the right side.

Why do we need both odd (i,i) and even (i,i+1) expansion calls?

Odd-length palindromes have a single character center (like 'aba'). Even-length palindromes have a two-character center (like 'abba'). Starting with left=right for odd and left=i, right=i+1 for even covers both cases.

Why must result be malloc'd in C instead of returning a pointer into s?

Returning s+start is valid if the caller never modifies s and never frees s separately. For safety, malloc+strncpy produces an independent null-terminated string the caller owns. The caller is responsible for free()ing it.

What is the time complexity and why is it O(n²) not O(n³)?

For each of the n centers, expansion is O(n) in the worst case (e.g., 'aaaa'). Total O(n²). The O(n³) brute force checks every substring separately — expand around center avoids redundant checking by growing outward from each center.

Visual Quiz - 4 Questions

For input 'cbbd', what does longestPalindrome return?

A cbbd

B bb

C b

D cbd

💡 Hint

Even expansion at i=1 (left=1,right=2): s[1]='b'==s[2]='b' → expand to left=0,right=3: s[0]='c'!=s[3]='d' → stop. len=2.

After expandCenter exits, left=-1 and right=5 for a string of length 5. What is the palindrome length?

A 4

B 5

C 6

D 3

💡 Hint

len = right - left - 1 = 5 - (-1) - 1 = 5.

For the even expansion call expandCenter(s, i, i+1, ...), what is the shortest palindrome it can find?

A Length 1

B Length 2

C Length 0

D Length 3

💡 Hint

If s[i] != s[i+1], the while loop never runs. right - left - 1 = (i+1) - i - 1 = 0. No even palindrome at this center.

Why does the algorithm initialize maxLen = 1 instead of 0?

A To avoid division by zero

B Every non-empty string has at least one character which is a palindrome of length 1

C Because odd expansion always finds length at least 1

D Both B and C

💡 Hint

A single character is always a palindrome. The odd expansion at any center always produces at least length 1, so starting at 1 is both correct and safe.

Concept Snapshot

Expand Around Center: for each position (and gap), expand outward while s[left]==s[right]. Palindrome is at indices left+1 to right-1 after loop exits. Two calls per position: odd (i,i) and even (i,i+1). Time O(n²), space O(1). In C: malloc result, use right-left-1 for length formula, cast to unsigned char if using ctype functions.

Full Transcript

Let's trace Longest Palindromic Substring on 'babad' using expand-around-center in C. We initialize start=0, maxLen=1. We loop i from 0 to 4. At i=1 with odd expansion: left=1, right=1. s[1]='a'==s[1]='a' — that's the single character, so we immediately try to expand. left becomes 0, right becomes 2. s[0]='b'==s[2]='b' — match, continue expanding. left becomes -1, right becomes 3. left < 0 so loop stops. On exit: len = right - left - 1 = 3 - (-1) - 1 = 3. That's greater than maxLen=1, so we update: maxLen=3, start = left+1 = 0. At i=2 with odd expansion: similarly produces len=3 starting at index 0 (for 'aba'). But 3 is not greater than 3, so start stays 0. Final: malloc 4 bytes, strncpy from s+0 length 3, null terminate. Return 'bab'. Key C rule: the palindrome boundaries after the loop are left+1 to right-1 — always apply this formula, never use the raw loop exit values directly.

Practice

1. What is the main goal when finding the Longest Palindromic Substring in a given string?

easy

A. To find the longest substring with all unique characters

B. To find the longest substring that contains only vowels

C. To find the longest continuous sequence of characters that reads the same backward and forward

D. To find the longest substring that is sorted alphabetically

Solution

1. Step 1: Understand palindrome definition

   A palindrome reads the same backward and forward, like 'madam' or 'racecar'.

2. Step 2: Identify substring requirement

   The substring must be continuous characters in the string, not scattered.

3. Final Answer:

   To find the longest continuous sequence of characters that reads the same backward and forward -> Option C

4. Quick Check:

   Longest palindromic substring = continuous palindrome [OK]

Hint: Look for continuous same backward-forward sequences [OK]

Common Mistakes:

• Confusing substring with subsequence
• Looking for unique characters instead of palindrome
• Ignoring continuity of characters

2. Which of the following C code snippets correctly initializes variables to find the longest palindromic substring length?

easy

A. int maxLength = 0; int start = -1; int len = strlen(s);

B. int maxLength = 1; int start = 0; int len = strlen(s);

C. int maxLength = 1; int start = 0; int len = length(s);

D. int maxLength = 1; int start = 0; int len = s.length;

Solution

1. Step 1: Check correct function for string length in C

   In C, strlen() is used to get string length, not length() or s.length.

2. Step 2: Verify variable initialization

   Longest palindrome length starts at 1 (single char), start index at 0, and length is string length.

3. Final Answer:

   int maxLength = 1; int start = 0; int len = strlen(s); -> Option B

4. Quick Check:

   Use strlen() for string length in C [OK]

Hint: Use strlen() to get string length in C [OK]

Common Mistakes:

• Using length() instead of strlen() in C
• Initializing maxLength to 0 instead of 1
• Using Java or C++ string length syntax in C

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

char s[] = "babad";
int maxLength = 1, start = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
    int low = i - 1;
    int high = i + 1;
    while (high < len && s[high] == s[i])
        high++;
    while (low >= 0 && s[low] == s[i])
        low--;
    while (low >= 0 && high < len && s[low] == s[high]) {
        low--;
        high++;
    }
    int length = high - low - 1;
    if (maxLength < length) {
        maxLength = length;
        start = low + 1;
    }
}
printf("%d", maxLength);

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Understand the palindrome expansion logic

   The code expands around each character to find palindromes, including duplicates and symmetric characters.

2. Step 2: Trace the longest palindrome in "babad"

   Longest palindromic substrings are "bab" or "aba", both length 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest palindrome in "babad" = 3 [OK]

Hint: Check palindrome centers and expand outwards [OK]

Common Mistakes:

• Assuming entire string is palindrome
• Counting non-continuous characters
• Ignoring multiple palindrome centers

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

char s[] = "cbbd";
int maxLength = 1, start = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
    int low = i - 1;
    int high = i + 1;
    while (low >= 0 && high < len && s[low] == s[high]) {
        low--;
        high++;
    }
    int length = high - low - 1;
    if (maxLength < length) {
        maxLength = length;
        start = low + 1;
    }
}
printf("%d", maxLength);

medium

A. The code does not check for even length palindromes correctly

B. The variable 'start' is not updated properly

C. The initial maxLength should be 0, not 1

D. The loops use wrong comparison operators

Solution

1. Step 1: Analyze palindrome detection logic

   The code expands around a single center character, missing even length palindromes like "bb" in "cbbd".

2. Step 2: Identify missing even length palindrome check

   Even length palindromes require checking centers between characters, which is not done here.

3. Final Answer:

   The code does not check for even length palindromes correctly -> Option A

4. Quick Check:

   Missing even length palindrome check = bug [OK]

Hint: Check centers between characters for even palindromes [OK]

Common Mistakes:

• Only checking odd length palindromes
• Not updating start index correctly
• Wrong initial maxLength value

5. Given the string "forgeeksskeegfor", which approach correctly finds the longest palindromic substring and what is its length? A) Brute force method, length 8 B) Dynamic programming method, length 12 C) Expand around center method, length 12 D) Expand around center method, length 10

hard

A. Brute force method, length 8

B. Dynamic programming method, length 12

C. Expand around center method, length 12

D. Expand around center method, length 10

Solution

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

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

2. Step 2: Check method correctness and length

   Expand around center method can find the longest palindrome correctly. The longest palindrome is "geeksskeeg" (length 10).

3. Step 3: Re-examine options

   Expand around center method, length 10 says expand around center method, length 10 which is correct. Other options have incorrect lengths or methods.

4. Final Answer:

   Expand around center method, length 10 -> Option D

5. Quick Check:

   Longest palindrome "geeksskeeg" length 10 [OK]

Hint: Longest palindrome is "geeksskeeg" length 10 [OK]

Common Mistakes:

• Assuming full string is palindrome
• Confusing length 12 with actual palindrome length
• Mixing method with incorrect length