Interview 150
Longest Palindrome
- Problem
- LC 409
- File
- interview150_LC409LongestPalindrome.java
- Path
- pkg5leetcode/interview150/interview150_LC409LongestPalindrome.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC409LongestPalindrome.java
- Approach
- Use pairs of chars plus one center if odd count exists.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Longest Palindrome | LC 4095 * APPROACH: Use pairs of chars plus one center if odd count exists.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC409LongestPalindrome {9 static int longestPalindrome(String s) {10 int[] cnt = new int[128];11 for (char c : s.toCharArray()) cnt[c]++;12 int len = 0, odd = 0;13 for (int x : cnt) {14 len += x / 2 * 2;15 if (x % 2 == 1) odd = 1;16 }17 return len + odd;18 }19 20 public static void main(String[] args) {21 check(longestPalindrome("abccccdd") == 7, "case1");22 check(longestPalindrome("a") == 1, "case2");23 System.out.println("all tests passed");24 }25 26 static void check(boolean cond, String name) {27 if (!cond) throw new AssertionError("FAILED: " + name);28 System.out.println(" PASS " + name);29 }30}