Longest Palindrome - Practice Coding Problems

Longest Palindrome - Problem

Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters.

Letters are case sensitive, for example, "Aa" is not considered a palindrome.

Input & Output

Example 1 — Basic Case

$ Input: s = "abccccdd"

› Output: 7

💡 Note: One longest palindrome is "dccaccd". We can use: 2 d's, 4 c's, and 1 a in the center.

Example 2 — Single Character

$ Input: s = "a"

› Output: 1

💡 Note: The longest palindrome is "a" itself, which has length 1.

Example 3 — All Pairs

$ Input: s = "aabbcc"

› Output: 6

💡 Note: All characters have even counts, so we can use all of them: "abccba" has length 6.

Constraints

1 ≤ s.length ≤ 2000
s consists of lowercase and/or uppercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String with mixed case letters: "abccccdd"

Process

Count frequencies and determine palindrome structure

Output

Maximum possible palindrome length: 7

Key Takeaway

🎯 Key Insight: A palindrome uses all even-count characters and at most one odd-count character in the center

Asked in

G Google 25 a Amazon 20 f Facebook 18 M Microsoft 15

The key insight is that a palindrome can have at most one character with odd count (placed in center) and all other characters must appear in pairs. The optimal approach counts character frequencies and calculates: sum of (even counts) + sum of (odd counts - 1) + (1 if any odd count exists). Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Permutations	O(n! × n)	O(n)	Generate all possible arrangements and check each for palindrome properties
Frequency Counting (Optimal)	O(n)	O(1)	Count character frequencies and calculate maximum palindrome length
Greedy Single Pass	O(n)	O(1)	Calculate palindrome length while counting characters in a single pass

Brute Force - Generate All Permutations — Algorithm Steps

Generate all permutations of the string
Check each permutation to see if it's a palindrome
Return the length of the longest palindromic permutation found

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Characters

Count frequency of each character in the string

Calculate Pairs

Use even counts fully, odd counts minus one

Add Center

Add one character for the center if any odd counts exist

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int charCount[128] = {0}; // ASCII characters
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        charCount[(int)s[i]]++;
    }
    
    int length = 0;
    int oddFound = 0;
    
    for (int i = 0; i < 128; i++) {
        if (charCount[i] > 0) {
            if (charCount[i] % 2 == 0) {
                length += charCount[i];
            } else {
                length += charCount[i] - 1;
                oddFound = 1;
            }
        }
    }
    
    if (oddFound) {
        length += 1;
    }
    
    return length;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove newline
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! permutations to generate, each taking O(n) time to check if palindrome

⚠ Quadratic Growth

Space Complexity

O(n)

Space to store current permutation being checked

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler