Question

Formatted question description: https://leetcode.ca/all/266.html

Given a string s, return true if a permutation of the string could form a palindrome and false otherwise.

Example 1:

Input: s = "code"
Output: false

Example 2:

Input: s = "aab"
Output: true

Example 3:

Input: s = "carerac"
Output: true

Constraints:

1 <= s.length <= 5000
s consists of only lowercase English letters.

Algorithm

Use HashSet to traverse the string

If a letter is not in the HashSet, we add this letter,
If the letter already exists, we delete the letter, So in the end, if there are no letters or only one letter in the HashSet, it means that it is a palindrome.

Code

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Palindrome_Permutation {

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

            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                map.put(c, 1 + map.getOrDefault(c, 0));
            }

            int count = 0;
            for (int each: map.values()) {
                if (each % 2 == 1) {
                    count++;
                }
            }

            return count < 2;
        }
    }

    public class Solution_set {
        public boolean canPermutePalindrome(String s) {

            Set<Character> hs = new HashSet<>();

            for (char each: s.toCharArray()) {
                if (hs.contains(each)) {
                    hs.remove(each);
                } else {
                    hs.add(each);
                }
            }

            return hs.size() <= 1;
        }
    }
}

############

class Solution {
    public boolean canPermutePalindrome(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        int n = 0;
        for (int v : cnt) {
            n += v % 2;
        }
        return n < 2;
    }
}

// OJ: https://leetcode.com/problems/palindrome-permutation/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    bool canPermutePalindrome(string s) {
        int cnt[26] = {}, single = 0;
        for (char c : s) cnt[c - 'a']++;
        for (int n : cnt) {
            single += n % 2;
            if (single > 1) return false;
        }
        return true;
    }
};

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        return sum(v % 2 for v in Counter(s).values()) <= 1

############

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        oddChars = set()

        for c in s:
            if c in oddChars:
                oddChars.remove(c)
            else:
                oddChars.add(c)

        return len(oddChars) <= 1

func canPermutePalindrome(s string) bool {
	cnt := make([]int, 26)
	for _, c := range s {
		cnt[c-'a']++
	}
	n := 0
	for _, v := range cnt {
		n += v & 1
	}
	return n < 2
}

/**
 * @param {string} s
 * @return {boolean}
 */
var canPermutePalindrome = function (s) {
    let ss = new Set();
    for (let c of s) {
        if (ss.has(c)) {
            ss.delete(c);
        } else {
            ss.add(c);
        }
    }
    return ss.size < 2;
};

266 - Palindrome Permutation

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions