CODEWITHSUNDEEP
javaalgorithmpalindrome
Julian
Julian

Reputation: 91

check if the characters of a string can be rearranged to make a palindrome

I am working on a problem from codesignal, which asks to determine whether the characters of a string can be rearranged to make a palindrome. My approach to this was creating a HashMap and placing each character of the string in it. If the HashMap contains an even sum of all the values, we must make sure each value itself is even. Otherwise, if the sum is odd, we need to see if one value at most was not even. I am currently passing 9/10 tests.

The test I am failing has the input: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbccccaaaaaaaaaaaaa". My solution outputs true when it should be false. I do not see where I am messing up.

boolean palindromeRearranging(String inputString) {
    
    HashMap<Character,Integer> letters=new HashMap<Character,Integer>();
    boolean isPalidrome=false;
    
    //one character strings are palindromes
    if(inputString.length()==1)
    {
        isPalidrome=true;
    }

    //look at the string and count the instances of each character
    for(int i=0;i<inputString.length();i++)
    {
        //add each character not in the hashmap already
        if(!letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), 1);
        }
        //otherwise, increment the count
        else if(letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), letters.get(inputString.charAt(i)) + 1);
        }
    }
    
    //sum the values in the hashmap
    int sum=0;
    Collection<Integer>val=letters.values();
    //count of values that are not even
    int v=0;
    
    for(int n:val)
    {
        //System.out.println("n:"+n);
        sum+=n;
        
        //if a value corresponding to a key isn't even, increase the count 
        if(sum%2!=0)
        {
            v++;
        }
    }
    
    //System.out.println(sum);
    
    //if we have an even sum then we have to make sure each key has an even value
    if(sum%2==0)
    {
        for(int n:val)
        {
            //if a key doesn't have an even value
            if(n%2!=0)
            {
                isPalidrome=false;
            }
            else
                isPalidrome=true;
        }
    }
    
    if(sum%2!=0)
    {
        if(v==1)
        {
            isPalidrome=true;
        }
        else
            isPalidrome=false;
    }
    
    return isPalidrome;

}

Upvotes: 0

Views: 2053

Answers (4)

fatih karaca
fatih karaca

Reputation: 1

 boolean solution(String str) {
        HashMap<String ,Integer> map=new HashMap<>();
        int count=0;
        int count1=0;
        for(String w:str.split("")){
            if(!map.containsKey(w)){
                map.put(w, 1);
            }
            else if(map.containsKey(w)){
                map.put(w, map.get(w)+1) ;}
        }
        boolean bool=false;
        for(Integer w: map.values()){
            if(w==1){
                count++;}
            else if(w%2==0){
                bool=true;}
            else if(w%2!=0){
                count1++;}
            bool=count>1||count1>1?false:true;
        }
        return bool;
    }

Upvotes: 0

user5849527
user5849527

Reputation:

Instead of calculating the sum of the hashmap values, below is my logic. Basically a palindrome can be formed with atmost one set of odd characters and can have any set of even characters. Lets say there is a string aaaabbccc. Here there are two sets of even characters(a & b) and one set of odd which can be a palindrome, if rearranged. Below is my program in c++.

#include <bits/stdc++.h>
using namespace std;

int main()
{
        string input;
        cin>> input;
        
        cout<< input<< endl;
        
        int a[26] = {0};

        for (int i = 0; input[i] != '\0'; i++)
            a[input[i] - 97]++;
        
        int odd = 0;
        for (int i = 0; i < 26; i++)
        {
            if (a[i] != 0)
            {
                if (a[i] % 2)
                {
                    odd++;
                    if (odd > 1)
                    {
                        cout<< "false"<< endl;
                        break;
                    }
                }
                
            }
        }

        if (odd < 2)
            cout<< "true"<< endl;
    return 0;
}

You can try this logic to check for a palindrome.

Upvotes: 1

amar_1995
amar_1995

Reputation: 595

You forget to add break in loop inside if(sum%2==0)

boolean palindromeRearranging(String inputString) {

    HashMap<Character,Integer> letters=new HashMap<Character,Integer>();
    boolean isPalidrome=false;
    
    //one character strings are palindromes
    if(inputString.length()==1)
    {
        isPalidrome=true;
    }

    //look at the string and count the instances of each character
    for(int i=0;i<inputString.length();i++)
    {
        //add each character not in the hashmap already
        if(!letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), 1);
        }
        //otherwise, increment the count
        else if(letters.containsKey(inputString.charAt(i)))
        {
            letters.put(inputString.charAt(i), letters.get(inputString.charAt(i)) + 1);
        }
    }
    
    //sum the values in the hashmap
    int sum=0;
    Collection<Integer>val=letters.values();
    //count of values that are not even
    int v=0;
    
    for(int n:val)
    {
        //System.out.println("n:"+n);
        sum+=n;
        
        //if a value corresponding to a key isn't even, increase the count 
        if(n%2!=0)
        {
            v++;
        }
    }
    
    //System.out.println(sum);
    
    //if we have an even sum then we have to make sure each key has an even value
    if(sum%2==0)
    {
        for(int n:val)
        {
            //if a key doesn't have an even value
            if(n%2!=0)
            {
                isPalidrome=false;
                break;
            }
            else
                isPalidrome=true;
        }
    }
    
    if(sum%2!=0)
    {
        if(v==1)
        {
            isPalidrome=true;
        }
        else
            isPalidrome=false;
    }
    
    return isPalidrome;

}

Upvotes: 1

Ehsan Gerayli
Ehsan Gerayli

Reputation: 594

In this part of your code

if(sum%2!=0)
    {
        v++;
    }

it should change to

if(n%2!=0)
    {
        v++;
    }

Upvotes: 1

Related Questions