How to determine whether a given string can be rearranged into a palindrome?

#computerscience #algorithms #ruby #rails

In this post, we'll create a simple method that checks whether a given string can be rearranged into a palindrome.
but first, let's make sure we know what a palindrome is

according to Wikipedia, A palindrome is a word, number, phrase, or another sequence of characters that reads the same backward as forward.

example: madam, racecar...

a simple method to check if a string is a palindrome using ruby would be

 def palindrome_check(str)
 return true if str==str.reverse
 end

constraints

with the previous definition in mind, we can lets create the constraints for our method,
A sting can be rearranged in a palindrome if:

It contains one or zero single character: the reason is that if we have one single character it can be in the middle of our string and it won't affect the result

example:

rac_e_car the e is in the middle and thus it won't affect our result

It contains one or zero characters with an odd number of occurrence in the string: the reason is that the permuting our characters we need to have the same number of characters of both sides left and right and having more than one character with an odd number of occurrences would affect our solution while splitting the string

examples:
A string like aaabbbb would be easily permuted to bb_aaa_bb which returns true

but with string like aaabbbbccc it would return false because we could not have the occurrence characters on both sides

with our contains being set let's write a simple ruby method that returns "YES" if a given string can be rearranged in a palindrome and "NO" if it's not the case


def palidrome_rearrange_check(str)
    arr=str.split("").uniq
    single=0
    odd=0
    arr.each do |x|
        single +=1 if str.count(x)==1
        odd +=1 if (str.count(x)).odd?
        return "NO" if single > 1
        return "NO" if odd > 1
    end
    return "YES"
end