Not passing hidden tests: checking if a string can be rearranged to form a palindrome

Question

I am trying to complete this question using a Stack: Given a string, find out if its characters can be rearranged to form a palindrome.

Example

For inputString = "aabb", the output should be solution(inputString) = true.

We can rearrange "aabb" to make "abba", which is a palindrome.

However, my code isn't passing 2 of the hidden tests and I am unsure as to why. Here is my code:

boolean solution(String inputString) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < inputString.length(); i++) {
        Character curr = inputString.charAt(i);
        if (stack.contains(curr) == false) {
            stack.push(curr);
        }
        else {
            stack.pop();
        }
    }
    if ((stack.size() == 0) || (stack.size() == 1)) {
        return true;
    }
    return false;
}

What is the error in my code?

Answer 1

False positive:

Consider the string "cabcc", which cannot be rearranged to form a palindrome. Your code will first push c then push a then push b then remove b (since it is a stack and it found c in cab) then remove a (since it found c in ca).

Since the stack has a length of 1, your program will output that cabcc can be rearranged into a palindrome when it cannot.

False negative

Consider the string "acac", which can be rearranged to form a palindrome (acca for instance). Your code will first push a then push c then remove c (since it is a stack and it found a in ac) then push c. Resulting in a stack containing ac.

Since the stack has a length of 2, your program will output that acac cannot be rearranged into a palindrome when it can.

How to fix

Do not use a stack. I suggest you use a map (check out hashmaps).