Given a string, find out if its characters can be rearranged to form a palindrome.

Example

For inputString = "aabb", the output should be

solution(inputString) = true.

We can rearrange "aabb" to make "abba", which is a palindrome.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] string inputString

  A string consisting of lowercase English letters.

  Guaranteed constraints:

  1 ≤ inputString.length ≤ 50.

• [output] boolean

  true if the characters of the inputString can be rearranged to form a palindrome, false otherwise.

풀이

• 파라미터 문자열이 회문이 가능한지 확인하는 문제
• 문자열 길이가 홀수 및 짝수일 경우에 따라 방법이 달라짐
• 자세한 풀이는 주석에 작성

boolean solution(String inputString) {
    // 문자열과 해당 문자열이 몇 개 존재하는지 기록하는 자료구조
    HashMap <Character, Integer> map = new HashMap<>();
    // 문자열에 포함된 문자 종류
    HashSet <Character> set = new HashSet<>();
    // 문자열 길이
    int length = inputString.length();
    
    // 각 자료구조에 저장
    for (int i = 0; i < length; i ++) {
        map.put(inputString.charAt(i), map.getOrDefault(inputString.charAt(i), 0) + 1);
        set.add(inputString.charAt(i));
    }
    
    // 홀 수가 존재했는지 확인하는 변수
    boolean isExistOdd = false;
    
    for (char c : set) {
        // 문자열 길이가 홀수일 때
        if (length % 2 > 0) {
            if (map.get(c) % 2 > 0) {
                // 홀 수가 두 번 나오면 회문은 성립할 수 없기에 실패
                if (isExistOdd) {
                    return false;
                } else {
                    // 홀 수 가 없었다면 중앙 배치가 가능하므로 변수 상태 변경
                    isExistOdd = true;
                }
            }
        } else {
            // 문자열이 짝수일 때,
            // 해당 문자의 개수가 홀 수면 실패
            if (map.get(c) % 2 > 0) return false;
        }
    }
    
    return true;
}