This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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

For example,

`"code"`

-> False, `"aab"`

-> True, `"carerac"`

-> True.

b'

\n## Solution

\n

\n#### Approach #1 Brute Force [Accepted]

\n

\n#### Approach #2 Using HashMap [Accepted]

\n

\n#### Approach #3 Using Array [Accepted]

\n

\n#### Approach #4 Single Pass [Accepted]:

\n

\n#### Approach #5 Using Set [Accepted]:

\n

\n

'
\n\n

\n\n

If a string with an even length is a palindrome, every character in the string must always occur an even number of times. If the string with an odd length is a palindrome, every character except one of the characters must always occur an even number of times. Thus, in case of a palindrome, the number of characters with odd number of occurences can\'t exceed 1(1 in case of odd length and 0 in case of even length).

\nBased on the above observation, we can find the solution for the given problem. The given string could contain atmost all the ASCII characters from 0 to 127. Thus, we iterate over all the characters from 0 to 127. For every character chosen, we again iterate over the given string and find the number of occurences, , of the current character in . We also keep a track of the number of characters in the given string with odd number of occurences in a variable .

\nIf, for any character currently considered, its corresponding count, , happens to be odd, we increment the value of , to reflect the same. In case of even value of for any character, the remains unchanged.

\nIf, for any character, the becomes greater than 1, it indicates that the given string can\'t lead to the formation of a palindromic permutation based on the reasoning discussed above. But, if the value of remains lesser than 2 even when all the possible characters have been considered, it indicates that a palindromic permutation can be formed from the given string .

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . We iterate constant number of times(128) over the string of length giving a time complexity of .

\n \n - \n
Space complexity : . Constant extra space is used.

\n \n

\n

**Algorithm**

From the discussion above, we know that to solve the given problem, we need to count the number of characters with odd number of occurences in the given string . To do so, we can also make use of a hashmap, . This takes the form .

\nWe traverse over the given string . For every new character found in , we create a new entry in the for this character with the number of occurences as 1. Whenever we find the same character again, we update the number of occurences appropriately.

\nAt the end, we traverse over the created and find the number of characters with odd number of occurences. If this happens to exceed 1 at any step, we conclude that a palindromic permutation isn\'t possible for the string . But, if we can reach the end of the string with lesser than 2, we conclude that a palindromic permutation is possible for .

\nThe following animation illustrates the process.

\n!?!../Documents/266_Palindrome_Permutation.json:1000,563!?!

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . We traverse over the given string with characters once. We also traverse over the which can grow upto a size of in case all characters in are distinct.

\n \n - \n
Space complexity : . The hashmap can grow upto a size of , in case all the characters in are distinct.

\n \n

\n

**Algorithm**

Instead of making use of the inbuilt Hashmap, we can make use of an array as a hashmap. For this, we make use of an array with length 128. Each index of this corresponds to one of the 128 ASCII characters possible.

\nWe traverse over the string and put in the number of occurences of each character in this appropriately as done in the last case. Later on, we find the number of characters with odd number of occurences to determine if a palindromic permutation is possible for the string or not as done in previous approaches.

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . We traverse once over the string of length . Then, we traverse over the of length 128(constant).

\n \n - \n
Space complexity : . Constant extra space is used for of size 128.

\n \n

\n

**Algorithm**

Instead of first traversing over the string for finding the number of occurences of each element and then determining the of characters with odd number of occurences in , we can determine the value of on the fly while traversing over .

\nFor this, we traverse over and update the number of occurences of the character just encountered in the . But, whevenever we update any entry in , we also check if its value becomes even or odd. We start of with a value of 0. If the value of the entry just updated in happens to be odd, we increment the value of to indicate that one more character with odd number of occurences has been found. But, if this entry happens to be even, we decrement the value of to indicate that the number of characters with odd number of occurences has reduced by one.

\nBut, in this case, we need to traverse till the end of the string to determine the final result, unlike the last approaches, where we could stop the traversal over as soon as the exceeded 1. This is because, even if the number of elements with odd number of occurences may seem very large at the current moment, but their occurences could turn out to be even when we traverse further in the string .

\nAt the end, we again check if the value of is lesser than 2 to conclude that a palindromic permutation is possible for the string .

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . We traverse over the string of length once only.

\n \n - \n
Space complexity : . A of constant size(128) is used.

\n \n

\n

**Algorithm**

Another modification of the last approach could be by making use of a for keeping track of the number of elements with odd number of occurences in . For doing this, we traverse over the characters of the string . Whenver the number of occurences of a character becomes odd, we put its entry in the . Later on, if we find the same element again, lead to its number of occurences as even, we remove its entry from the . Thus, if the element occurs again(indicating an odd number of occurences), its entry won\'t exist in the .

\nBased on this idea, when we find a character in the string that isn\'t present in the (indicating an odd number of occurences currently for this character), we put its corresponding entry in the . If we find a character that is already present in the (indicating an even number of occurences currently for this character), we remove its corresponding entry from the .

\nAt the end, the size of indicates the number of elements with odd number of occurences in . If it is lesser than 2, a palindromic permutation of the string is possible, otherwise not.

\nBelow code is inspired by @StefanPochmann

\n\n**Complexity Analysis**

- \n
- \n
Time complexity : . We traverse over the string of length once only.

\n \n - \n
Space complexity : . The can grow upto a maximum size of in case of all distinct elements.

\n \n

\n

Analysis written by: @vinod23

\n