Java 1ms O(n) time, O(1) space solution.


  • 4
    C

    To achieve O(1) space, an int array is used to count how many time each char has appeared. Notice that the array is of length 128, which holds only for standard ASCII chars.

    public boolean canPermutePalindrome(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        int[] chars = new int[128];
        for (char c : s.toCharArray()) {
            chars[(int) c]++;
        }
        
        int count = 0;
        for (int i : chars) {
            if (i % 2 == 1) {
                count++;
            }
        }
        if (count > 1) {
            return false;
        }
        return true;
    }

  • 1
    G

    Small (stylish) improvements:

    if (i % 2 == 1) {
        count++;
    }
    

    could be replaced with:

    count += i % 2;
    

    and

    if (count > 1) {
        return false;
    }
    return true;
    

    with

    return count <= 1;

Log in to reply
 

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