Greedy: Given a string, return the length of longest palindrome

Problem Statement:

Given a string, return the length of longest palindrome substring that can be constructed with those letters

Palindrome are case sensitive, “Aa” is not a palindrome

Example:

Input: s = "aba"
Output: 3

Solution Explanation:

The solution for this problem is to find the longest palindromic substring by re-arranging the string.

For the solution, we will use frequency count for each letter in the string.

Then for each character if the frequency is odd, then it can be part of the palindromic substring only once, so subtract from the frequency array and add it to result.

If the frequency is even, then it can be added as many times of its frequency.

So add its frequency to the total length.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int solution(string s) 
{
    int res = 0, val = 0;
    unordered_map<char, int> mp;

    for (char ch : s) 
    {
        mp[ch]++;
    }

    for (auto entry : mp) 
    {
        if (entry.second % 2 != 0) 
        {
            res += entry.second - 1; 
            val = 1; // only one odd can go in the center
        } 
        else 
        {
            res += entry.second;
        }
    }
    return res + val;
}


int main() 
{
    string str = "aba";

    cout <<solution(str);
}

Output

3