Longest Palindromic Substring in DSA C - Build from Scratch

Longest Palindromic Substring

📖 Scenario: Imagine you are building a text analysis tool that finds the longest palindrome inside a given word or sentence. A palindrome is a sequence of characters that reads the same backward as forward, like "madam" or "racecar".

🎯 Goal: Build a program in C that finds and prints the longest palindromic substring from a given string.

📋 What You'll Learn

Create a character array called input with the exact value "babad"

Create an integer variable called max_len initialized to 1

Create two integer variables called start and len initialized to 0

Write a function expandAroundCenter that takes the string, left index, and right index, and returns the length of the palindrome expanding around those centers

Use a loop to check all possible centers in the string using expandAroundCenter

Update start and max_len when a longer palindrome is found

Print the longest palindromic substring using printf

💡 Why This Matters

🌍 Real World

Finding palindromic sequences is useful in text analysis, DNA sequence analysis, and data validation.

💼 Career

Understanding string manipulation and substring search is important for software developers working on text processing, search engines, and bioinformatics.

1

Create the input string

Create a character array called input and initialize it with the exact string "babad".

DSA C

# Create the input string
// Your code here

Hint

Use char input[] = "babad"; to create the string.

2

Add variables to track palindrome info

Add integer variables called start and max_len. Initialize start to 0 and max_len to 1.

DSA C

#include 

char input[] = "babad";

// Add variables to track palindrome start and max length
// Your code here

Hint

Use int start = 0; and int max_len = 1;.

3

Write the expandAroundCenter function

Write a function called expandAroundCenter that takes char *s, int left, and int right. It should expand while s[left] equals s[right] and return the length of the palindrome found.

DSA C

#include 

char input[] = "babad";

int start = 0;
int max_len = 1;

// Write expandAroundCenter function
// Your code here

Hint

Use a while loop to expand left and right indices while characters match.

4

Find and print the longest palindromic substring

Write a main function. Use a for loop with i from 0 to length of input - 1. For each i, call expandAroundCenter(input, i, i) and expandAroundCenter(input, i, i + 1). Update start and max_len if a longer palindrome is found. Finally, print the longest palindrome substring using printf("%.*s\n", max_len, input + start);

DSA C

#include 

char input[] = "babad";

int start = 0;
int max_len = 1;

int expandAroundCenter(char *s, int left, int right) {
    while (left >= 0 && s[right] != '\0' && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;
}

// Write main function to find and print longest palindrome
// Your code here

Hint

Use strlen to get string length. Use printf("%.*s\n", max_len, input + start); to print the substring.