Grind75
문제로

풀이

시간 복잡도 $O(2^n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap();

        for(char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) +1);
        }

        int result = 0;

        for(int i : map.values()) {
            if(i % 2 == 0) result = result + i;
            else if(i-1 != 0 && (i -1) % 2 == 0) result = result + (i - 1); // ccc
        }

        for(int i : map.values()) {
            if(i % 2 == 1) return result + 1;
        }

        return result;
    }
}

image

풀이2

 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

class Solution {
    public int longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        HashMap<Character, Integer> charCountMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
        }

        int length = 0;
        boolean oddFound = false;

        for (int count : charCountMap.values()) {
            if (count % 2 == 0) {
                length += count;
            } else {
                length += count - 1;
                oddFound = true;
            }
        }

        if (oddFound) {
            length += 1;
        }

        return length;
    }
}

image