aboutsummaryrefslogtreecommitdiff
path: root/longest_palindrome.c
diff options
context:
space:
mode:
Diffstat (limited to 'longest_palindrome.c')
-rw-r--r--longest_palindrome.c27
1 files changed, 27 insertions, 0 deletions
diff --git a/longest_palindrome.c b/longest_palindrome.c
new file mode 100644
index 0000000..d64c06d
--- /dev/null
+++ b/longest_palindrome.c
@@ -0,0 +1,27 @@
+// 409. Longest Palindrome
+#include "leetcode.h"
+
+/*
+ * given a sting '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
+ */
+
+int longestPalindrome(char *s) {
+ static int freq[128];
+ int mirror = 0, centre = 0;
+ memset(freq, 0, sizeof(freq));
+ while (*s != '\0')
+ ++freq[*s++];
+ for (int i = 0; i < 128; ++i) {
+ mirror += freq[i] / 2;
+ centre |= freq[i] & 1;
+ }
+ return mirror * 2 + centre;
+}
+
+int main() {
+ char *s1 = "abccccdd", *s2 = "a";
+ printf("%d\n", longestPalindrome(s1)); // expect: 7
+ printf("%d\n", longestPalindrome(s2)); // expect: 1
+}