Sponsored
Sponsored
This approach involves counting the frequency of each character in the string and calculating the length of the longest possible palindrome based on those frequencies. The key insight is that even frequency counts can completely contribute to a palindrome, while only one odd frequency character can be used once in the center of the palindrome.
Time Complexity: O(n) - where n is the length of the string as we iterate through the string to count character frequencies.
Space Complexity: O(1) - We only use a fixed-size array of 128 elements to store character frequencies.
1#include <stdio.h>
2#include <string.h>
3
4int longestPalindrome(char* s) {
5 int frequency[128] = {0};
6 for (int i = 0; s[i] != '\0'; ++i) {
7 frequency[s[i]]++;
8 }
9 int length = 0;
10 for (int i = 0; i < 128; i++) {
11 length += (frequency[i] / 2) * 2;
12 if (frequency[i] % 2 == 1 && length % 2 == 0) {
13 length++;
14 }
15 }
16 return length;
17}
18
19int main() {
20 char s[] = "abccccdd";
21 printf("%d\n", longestPalindrome(s)); // Output: 7
22 return 0;
23}This C program counts the frequency of each character using an array and then calculates the longest palindrome length by adding pairs of characters. If there's an odd frequency character, it is used as a center of the palindrome once, if needed.
This approach leverages a set data structure to efficiently keep track of characters with odd frequencies. A character encountered an odd number of times will toggle its presence in the set. The result is derived from the total number of characters and the size of this set.
Time Complexity: O(n) - Each character is processed independently.
Space Complexity: O(1) - Fixed memory allocation for set representation.
1using System;
using System.Collections.Generic;
class LongestPalindromeSet {
public static int LongestPalindrome(string s) {
HashSet<char> oddSet = new HashSet<char>();
foreach (char c in s) {
if (oddSet.Contains(c)) {
oddSet.Remove(c);
} else {
oddSet.Add(c);
}
}
int oddCount = oddSet.Count;
return s.Length - oddCount + (oddCount > 0 ? 1 : 0);
}
static void Main() {
string s = "abccccdd";
Console.WriteLine(LongestPalindrome(s)); // Output: 7
}
}C# leverages HashSet to accurately track odd count influence on the potential palindrome's size.