Can a string have a palindrome, is there a better way to do this?

Question

Today I had a very interesting question:

Given a string, you must determine if this string can have a palindrome when swapping.

Below is the implementation with which I came. But is there a better solution?

function canBePalindrome(someStr) { if (typeof someStr !== "string") { throw new Error("Expecting argument to be a string !"); } if (someStr.length == 1) return someStr; var canBePalin = false; var _chunks = someStr.split(""); var _length = _chunks.length; for (var i = 0; i < _length; i++) { for (var j = i + 1; j < _length; j++) { var temp_char = _chunks[i]; _chunks[i] = _chunks[j]; _chunks[j] = temp_char; if (isPalindrome(_chunks.join(""))) return true; } } return canBePalin; } //End of canBePalindrome function isPalindrome(someStr) { //console.log("Checking for:"+someStr); var original = someStr.split(""); return someStr === original.reverse().join(""); } //End of isPalindrome canBePalindrome("mdadm"); 

This would not be a possible duplication, because I do not check if it is a palindrome directly, but rearranges and checks it.

Answer 1

Save the character map, count them and check if the count is even for all characters, if so, you can create a palindrome

 function canBePalindrome(someStr) { var map = {}; var arr = someStr.split(''); arr.forEach(function(s) { s in map ? map[s]++ : map[s] = 1; }); var len = Object.keys(map).filter(function(o) { return map[o] % 2; }).length; return arr.length % 2 ? len === 1 : len === 0; } 

Fiddle

In the above version, "golfing" will

 function canBePalindrome(someStr) { return (function(m, a, l) { a.forEach(function(s) { s in m ? m[s]++ : m[s] = 1 }); l = Object.keys(m).filter(function(o) { return m[o] % 2 }).length; return a.length % 2 ? l === 1 : l === 0; })({}, someStr.split('')); } 

Answer 2

If all letters in a string have an even count, with the exception of no more than one, you can always reorganize them into a palindrome. My solution is a bit longer than the others, because I tried to minimize the overhead of loop performance with functions and unnecessary array creation.

 aaaabbbb => aabbbbaa aaaabbbbc => aabbcbbaa function isPalindromable(str) { var map = getCharCount(str); var nonPairs = 0; for (var char in charMap) { if (charMap[char] % 2 != 0) nonPairs++; if (nonPairs > 1) return false; } return true; } function getCharCount(str) { // Number of times each string appeared var map = {}; for (var i = 0; i < str.length; i++) { var ch = str.charAt(i); map[ch] = ++map[ch] || 1; } return map; } 

If you like one liner (not so fast, but elegant)

 function isPalindromable(str) { var charMap = getCharCountMap(str); return Object.keys(charMap).filter(char => charMap[char] %2 > 0).length <= 1; } function getCharCountMap(str) { return str.split('').reduce((prev, cur) => (prev[cur] = ++prev[cur] || 1, prev) , {}) } 

Performance editing

I compared three solutions. Mine was the slowest when the strings were short, and faster for longer strings. However, a friend at work came up with a solution that would ultimately be the fastest, perhaps because it has only one cycle, but does not need to be sorted. http://jsperf.com/can-string-be-made-into-palindrome/2

 function canBePalindromeReplace(string) { var oddCount = 0; while(string.length > 0) { var char = string.charAt(0); var stringLength = string.length; string = string.replace(new RegExp(char, 'g'), ''); var diff = stringLength - string.length; if((diff % 2) != 0) { oddCount++; if(oddCount > 1) { return false; } } } return true; } 

Answer 3

Solution using sorting and stack:

 function canBePalindrome(someStr) { var stack = []; someStr.split('').sort().forEach(function(ch) { stack[stack.length - 1] === ch ? stack.pop() : stack.push(ch); }); return stack.length < 2; } 

Answer 4

A good trick is to view the following palindrome properties:

• When the string size is a pair, all characters should appear a couple of times.
• When the line size is odd, then all characters , but one should appear a couple of times.

Using this information, you can write an algorithm to count the time when all possible char appear on the line, and then see if it matches the previous properties. This algorithm should have a time complexity of O(N + M) , where N is the size of the string and M is the number of possible characters that can be displayed in your string. For example, if a string contains only ASCII characters, then it has a time complexity of O(N + 255) . The complexity of the space is O(N + M) .

Answer 5

I think the best way is to create an array of length 26, arr[26] . One for each letter. Then go through the line, increasing the frequency of each letter as it occurs.

Having done this, go through arr[] and make sure that all frequencies are even or not. There is room for one character with an odd frequency, which we can put in the middle of the palindrome.

If all frequencies are even, then it can be organized as a palindrome.

Otherwise, no.

---

The algorithm should look something like this:

 str[] holding the string; create arr[26] and intialize with 0; for char in str: arr[char]++ //char should be mapped to its index properly // like a = 0, b = 1 and so on no_of_odd_char = 0 for freq in arr: if(freq % 2 == 1) if(no_of_odd_char == 1) print "cannot be palindrome" exit() else if(no_of_odd_char == 0) no_of_odd_char = 1 print "can be palindrome" 

Answer 6

There is a permutation of the string, which is a palindrome if the number of characters that appear an odd number of times is 0 or 1.

 function canBePalindrome(str) { var isOdd = Object.create(null), numOdd = 0; for(let ch of str) numOdd += (isOdd[ch] = !isOdd[ch]) * 2 - 1; return numOdd <= 1; } 

You can iterate with for(var i=0; i<str.length; ++i) to support pre-ES6 implementations, but this will not work properly if the line contains Unicode code outside the first 16 bits code point range.