Solution1 (hashmap + counter) class Solution { public boolean canPermutePalindrome(String s) { if (s == null || s.length() == 0) { return true; } int oddCount = 0; Map<Character, Integer> map = new HashMap<>(); for (Character c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); oddCount += map.get(c) % 2 == 0 ? -1 : 1; } return oddCount < 2; } } Solution2 (set) class Solution { public boolean canPermutePalindrome(String s) { Set<Character> set = new HashSet<>(); for (Character c : s.toCharArray()) { if (set.contains(c)) { set.remove(c); } else { set.add(c); } } return set.size() <= 1; } } note time O(n) space O(n) for both method The idea is to know that a palindrome string at most have one odd number of characters.