409. Longest palindrome

Address ：

Power button https://leetcode-cn.com/problems/longest-palindrome/

subject ：

Given a string of uppercase and lowercase letters  s , return   Constructed from these letters The longest palindrome string  .

In the process of construction , Please note that Case sensitive . such as  "Aa"  Can't be treated as a palindrome string .

Example 1:

Input :s = "abccccdd" Output :7 explain : The longest palindrome string we can construct is "dccaccd", Its length is 7.

Example 2:

Input :s = "a" Input :1

Example 3:

Input :s = "bb" Input : 2

Tips :

1 <= s.length <= 2000 s  Only lowercase and / Or capital letters

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/longest-palindrome
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

Palindromes mean pairs , Even number , As for whether there is an odd number in the middle , All palindromes

So we use the idea of counting arrays to complete

Count array can refer to ：

Counting sorting of sorting algorithm

Method 1 、 Count array

int longestPalindrome(char * s){
	int count[58]={0};
	int cnt = 0;
	int odd = 0;
	int i = 0;
	
	while(s[i])
	{
		int idx = s[i] - 'A';
		//printf("s[%d]=%d, idx=%d\n", i, s[i], idx);
		count[idx]++;
		i++;
	}
	
	for(i=0; i<58; i++)
	{
		if(count[i] != 0)
		{
			if(count[i] & 1)
				odd = 1;
			cnt += count[i] / 2;
		}
	}
	
	cnt *= 2;
	
	if(odd == 1)
		cnt++;
		
	return cnt;
}

See more brush notes