Java Bit Manipulation Solution (one test case left, which contains characters other than alphabets)


  • 0
    C

    If the input string only contains lower case or upper case alphabets, the below solution could be a better one, time complexity is O(n + 26), n is the length of input string, space is O(1).

    But unfortunately, the last test case contains '/' '' '-' characters.

    I think I have to use hash map to solve the problem.

    public boolean canPermutePalindrome(String s) {

        if(s == null) {
            return true;
        }
        
        int len = s.length();
        int upper = 0;
        int lower = 0;
        for(int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if(c - 'a' >= 0 && c - 'a' < 26) {
                lower ^= 1 << (c - 'a');
            } else {
                upper ^= 1 << (c - 'A');
            }
        }
        
        if(len % 2 == 0) {
            return lower == 0 && upper == 0;
        }
        
        int countUpper = 0;
        int countLower = 0;
        for(int i = 0; i < 26; i++) {
            int mask = 1 << i;
            if((upper & mask) != 0) {
                countUpper++;
            }
            if((lower & mask) != 0) {
                countLower++;
            }
        }
        
        return (countUpper == 1 && countLower == 0) || (countUpper == 0 && countLower == 1);
    }
    

    alternative solution using hash map:

    public boolean canPermutePalindrome(String s) {

        if(s == null) {
            return true;
        }
        
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0; i < s.length(); i++) {
            int count = 1;
            if(map.containsKey(s.charAt(i))) {
                count += map.get(s.charAt(i));
            }
            map.put(s.charAt(i), count);
        }
        
        Set<Character> keySet = map.keySet();
        int oddCount = 0;
        for(char key : keySet) {
            int count = map.get(key);
            if(count % 2 != 0) {
                oddCount++;
            }
        }
        
        if(s.length() % 2 == 0) {
            return oddCount == 0;
        } else {
            return oddCount == 1;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.