Find length of the longest palindrome possible from a string
Given a string, find the length of the longest palindrome possible from its characters.
For example,
Output: 5
Explanation: The longest palindrome is ACBCA or ACDCA or CABAC or CADAC, each having length 5
Input: str = AA
Output: 2
Explanation: The longest palindrome is AA, having length 2
A palindrome string consists of characters in pairs, except for one that may form the middle character. The i’th character from the start of the palindrome is the same as the i’th character from the end of the palindrome. There may or may not be a middle character, and it can be any character.
The idea is to count the even and odd frequency characters in a string and use that information to construct the longest palindrome possible. For any character with an even count, half of the characters will fit in the left half of the palindrome, and the other half will fit in the right. The middle element can be made up of any character with an odd count. Any character with an odd count of three or more can be divided into even frequency pairs and a single character.
This logic can be easily implemented using hashing, using a map or a set.
1. Using Map
The idea is to create a frequency map to hold the count of each character in the string. Then, obtain the count of the even-frequency characters by iterating through the map’s values. Increase the count if the string contains an odd-frequency character, as it can form the middle character of the palindrome.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <iostream> #include <string> #include <unordered_map> using namespace std; int findLongestPalindromeLength(string str) { // base case: empty string if (str.empty()) { return 0; } // create a frequency map to store count of each character in the string unordered_map<int, int> freq; for (char c: str) { freq[c]++; } // stores the count of even-frequency characters in the string int result = 0; // true if the string contains any odd-frequency character bool hasOdd = false; // iterate through the map's values for (auto &p: freq) { // increment the result by even-frequency character's count result += (p.second / 2) * 2; // update the flag if the string contains any odd-frequency character if (p.second % 2 == 1) { hasOdd = true; } } // increment the count if the string has odd character return result + (hasOdd? 1: 0); } int main() { string str = "ABACCD"; cout << "The length of the longest palindrome is " << findLongestPalindromeLength(str); return 0; } |
Output:
The length of the longest palindrome is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; class Main { public static int findLongestPalindromeLength(String str) { // base case: empty string if (str == null || str.isEmpty()) { return 0; } // create a frequency map to store count of each character in the string Map<Character, Integer> freq = new HashMap<>(); for (char c: str.toCharArray()) { freq.put(c, freq.getOrDefault(c, 0) + 1); } // stores the count of even-frequency characters in the string int result = 0; // true if the string contains any odd-frequency character boolean hasOdd = false; // iterate through the map's values for (int c: freq.values()) { // increment the result by even-frequency character's count result += (c / 2) * 2; // update the flag if the string contains any odd-frequency character if (c % 2 == 1) { hasOdd = true; } } // increment the count if the string has odd character return result + (hasOdd? 1: 0); } public static void main(String[] args) { String str = "ABACCD"; int length = findLongestPalindromeLength(str); System.out.println("The length of the longest palindrome is " + length); } } |
Output:
The length of the longest palindrome is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
def findLongestPalindromeLength(str): # base case: empty string if not str: return 0 # create a frequency map to store count of each character in the string freq = {} for c in str: freq[c] = freq.get(c, 0) + 1 # stores the count of even-frequency characters in the string result = 0 # true if the string contains any odd-frequency character has_odd = False # iterate through the dictionary values for cnt in freq.values(): # increment the result by even-frequency character's count result += (cnt # 2) * 2 # update the flag if the string contains any odd-frequency character if cnt % 2 == 1: has_odd = True # increment the count if the string has odd character return result + (1 if has_odd else 0) if __name__ == '__main__': str = 'ABACCD' print('The length of the longest palindrome is', findLongestPalindromeLength(str)) |
Output:
The length of the longest palindrome is 5
The time complexity of the above solution is O(n) and requires O(n) extra space for map, where n is the length of the string.
2. Using Set
Alternatively, we can maintain a set to store the unpaired characters in the string and a counter to store the number of pairs. The idea is to iterate over the string, and if the current character is already present in the set, remove it and increase the pair count by one; otherwise, include the current character in the set. The longest palindrome will now have two characters from each pair, one for the left side and one for the right. Any remaining characters in the set can be placed in the middle of the palindrome string.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> #include <string> #include <unordered_set> using namespace std; int findLongestPalindromeLength(string str) { // base case: empty string if (str.empty()) { return 0; } // create a set to store unpaired characters in the string unordered_set<char> chars; // store number of pairs int pairs = 0; // iterate over characters of the string for (char c: str) { // if the current character already exists in the set if (chars.find(c) != chars.end()) { // remove current character from the set and increment pair count by 1 chars.erase(c); pairs++; } // otherwise, add the current character in the set else { chars.insert(c); } } // each pair contributes a character to left and right half of the palindrome // any character left in the set can form the middle character of the palindrome return pairs * 2 + (chars.empty() ? 0: 1); } int main() { string str = "ABACCD"; cout << "The length of the longest palindrome is " << findLongestPalindromeLength(str); return 0; } |
Output:
The length of the longest palindrome is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import java.util.HashSet; import java.util.Set; class Main { public static int findLongestPalindromeLength(String str) { // base case: empty string if (str == null || str.isEmpty()) { return 0; } // create a set to store unpaired characters in the string Set<Character> chars = new HashSet<>(); // store number of pairs int pairs = 0; // iterate over characters of the string for (char c : str.toCharArray()) { // if the current character already exists in the set if (chars.contains(c)) { // remove current character from the set and increment pair count by 1 chars.remove(c); pairs++; } // otherwise, add the current character in the set else { chars.add(c); } } // each pair contributes a character to left and right half of the palindrome // any character left in the set can form the middle character of the palindrome return pairs * 2 + (chars.isEmpty() ? 0: 1); } public static void main(String[] args) { String str = "ABACCD"; int length = findLongestPalindromeLength(str); System.out.println("The length of the longest palindrome is " + length); } } |
Output:
The length of the longest palindrome is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
def findLongestPalindromeLength(str): # base case: empty string if not str: return 0 # create a set to store unpaired characters in the string chars = set() # store number of pairs pairs = 0 # iterate over characters of the string for c in str: # if the current character already exists in the set if c in chars: chars.remove(c) # remove current character from the set pairs = pairs + 1 # increment pair count by 1 # otherwise, add the current character in the set else: chars.add(c) # each pair contributes a character to left and right half of the palindrome # any character left in the set can form the middle character of the palindrome return pairs * 2 + (1 if chars else 0) if __name__ == '__main__': str = 'ABACCD' print('The length of the longest palindrome is', findLongestPalindromeLength(str)) |
Output:
The length of the longest palindrome is 5
The time complexity of the above solution is O(n) and requires O(n) extra space for set, where n is the length of the string.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)