algorithm notes: leetcode#266 palindrome permutation

Problem

Given a string, determine if a permutation of the string could form a palindrome.

Example 1:

Input: "code"
Output: false

Example 2:

Input: "aab"
Output: true

Example 3:

Input: "carerac"
Output: true

Soultion

Analysis

If a string can form a palindrome, it should contain characters with even number of occurences and one character with odd number of occurences , or only characters with even number of occurences.

We can use set to record the characters with odd number of occurences. Traverse the given string s, if we meet a character odd number of times, put it in the set, otherwise remove it. Return whether the number of characters in the set is 0 or 1.

Python implementation

1
2
3
4
5
6
7
8
9
10
11
12
13

class :
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        left = set()
        for c in s:
            if c in left:
                left.remove(c)
            else:
                left.add(c)
        return len(left) < 2

Java implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class  {
    public boolean canPermutePalindrome(String s) {
        Set<Character> left = new HashSet<>();
        
        for(int i = 0; i < s.length(); i++){
            if(left.contains(s.charAt(i))){
                left.remove(s.charAt(i));
            }else {
                left.add(s.charAt(i));
            }
        }
        
        return left.size() < 2;
    }
}

Time complexity

O(n). n is length of string s, as we traverse each character in it.

Space complexity

O(1). For worst case, the set has all unique letters, total number of which is fixed.

Link

266. Palindrome Permutation
(中文版)