C++ Program to Find the Longest Palindrome in a String (C++) with Explanation

Find the Longest Palindrome in a String (C++)

Hard C++ Variables 22 views

c++ string palindrome loops hard

Explanation Complexity

Problem Statement

In this problem, you will write a C++ program to find the longest palindromic substring in a given string.
A palindrome is a string that reads the same forward and backward.
You will use variables, loops, and string operations to solve this problem.
This question helps you practice strings, nested loops, and logical thinking in C++.

Input Format

A single string.

Output Format

Print the longest palindromic substring.

Example

Input

meetcodesiik

Output

meetcodesiik

Constraints

1 ≤ length of string ≤ 1000

Concept Explanation

In C++, a string is a sequence of characters.
A palindrome is a string that is the same when reversed.

Examples of palindromes are:
madam, level, aba

To find the longest palindromic substring, we check all possible substrings.
For each position in the string, we try to expand around the center.
There are two cases:

Odd length palindrome (center at one character)

Even length palindrome (center between two characters)

We keep track of the maximum length palindrome found so far.
This problem needs careful use of loops and index handling.
It is a common hard-level interview question.

Step-by-Step Explanation

Step 1: Understand the goal: find the longest palindrome.
Step 2: Choose the main idea: expand around center.
Step 3: Take input string from the user.
Step 4: Loop through each character as center.
Step 5: Expand left and right to check palindrome.
Step 6: Update longest palindrome length and start index.
Step 7: Print the longest palindromic substring.

Complexity Analysis

Time

O(N²)

Space

O(1)

Common Mistakes

Input: "babad"
Output: "bab"

Concept Explanation

Step-by-Step Explanation

Input / Output Format

Input Format

A single string.

Output Format

Print the longest palindromic substring.

Constraints

1 ≤ length of string ≤ 1000

Examples

Input:

meetcodesiik

Output:

meetcodesiik

Example Solution (Public)

C++

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

int main() {
    string s;
    cout << "Enter a string: ";
    cin >> s;

    int n = s.length();
    int start = 0, maxLen = 1;

    for (int i = 0; i < n; i++) {
        // Odd length palindrome
        int left = i, right = i;
        while (left >= 0 && right < n && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }

        // Even length palindrome
        left = i;
        right = i + 1;
        while (left >= 0 && right < n && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }
    }

    cout << "Longest Palindrome: ";
    for (int i = start; i < start + maxLen; i++) {
        cout << s[i];
    }

    return 0;
}

Official Solution Code

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

int main() {
    string s;
    cout << "Enter a string: ";
    cin >> s;

    int n = s.length();
    int start = 0, maxLen = 1;

    for (int i = 0; i < n; i++) {
        // Odd length palindrome
        int left = i, right = i;
        while (left >= 0 && right < n && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }

        // Even length palindrome
        left = i;
        right = i + 1;
        while (left >= 0 && right < n && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }
    }

    cout << "Longest Palindrome: ";
    for (int i = start; i < start + maxLen; i++) {
        cout << s[i];
    }

    return 0;
}

Please login to submit solutions.