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.