Palindrome Permutation


  • 0

    Click here to see the full article post


  • 0
    M

    another solution is bit manipulation.
    Space complexity is O(1)
    time complexity O(n)


  • 0
    N

    "aab" was Palindrome Permutation? The description maybe wrong, am I right?


  • 0
    M

    @Nu1L "aab" is not Palindrome but it is Palindrome Permutation


  • 0
    R

    @vinod23 ,@mrkingdom75 can you please explain how 'abcab' it can be a palindrome permutation?since a and b appears even time and c appear once which is fine but it is not palindrome anymore even though permutation is fine.


  • 0
    M

    hi @ramsiddarth , it's same with my answer for @Nu1L 'aab' is not Palindrome but is Palindrome Permutation because 'aab' -> 'aba',

    So same with input 'abcab' is Palindrome Permutation because after you permute 'abcab' it becomes 'abcba' , and 'abcba' is Palindrome

    Hope my answer can help you


  • 0
    R

    @mrkingdom75 make sense so with even number of same character and one odd character we can say the string should be palindrome.


  • 0
    M

    The space complexity of Approach #5 should not be O(n). It should be O(128). If you make assumption that "String only contains ASCII characters from 0 to 127", this should be true in this approach too.According to the pigeonhole principle, the set size could only be 128 or less.


  • 0
    P
    //Store all the values in map, now if it is a palindrome then all the char should have even number and only one can have odd depending upong the length of a string, if length is odd then there will be one element which will have odd count, if length is even then all char should have even length
    
    class Solution {
        public boolean canPermutePalindrome(String s) {
            
            Map<Character,Integer> map = new HashMap<>();
            for (char ch : s.toCharArray()){
                if (map.containsKey(ch)){
                    int temp = map.get(ch);
                    map.put(ch,temp+1);
                }else map.put(ch,1);                                    
            }
            
            boolean isValid = false;
            
            for (char ch : map.keySet()){
                if (map.get(ch)%2==0)
                    continue;            
                if ((map.get(ch)%2==1)&&(isValid == true)){
                    return false;
                }else if (map.get(ch)%2==1){
                    isValid = true;
                    continue;
                }
            }
            return true;                        
        }
    }

  • 0
    V

    Such an elegant solution (#5)


Log in to reply
 

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