Palindrome Permutation

Given a string s), check if the characters of the given string can be rearranged to form a palindrome.

Input: s = "carrace"
Output: True
Explanation: The string can be converted into a palindrome: racecar.

Input: s = "amazon"
Output: False
Explanation: More than one character has odd frequency, so it cannot form a palindrome.

Common Idea used in all approaches : A set of characters can form a palindrome if at most one character occurs an odd number of times and all characters occur an even number of times.

[Naive Approach] Using Two Loop - O(n^2) Time and O(1)

The idea is to count the frequency of each character using a simple brute force method. For every character in the string, we check how many times it appears by comparing it with all other characters (using two loops). For a string to form a palindrome, most characters should appear an even number of times, and at most one character can have an odd frequency. While counting, we keep track of how many characters have odd counts. If more than one character has an odd count, it is not possible to form a palindrome; otherwise, it is possible.

#include <iostream>
#include <string>
using namespace std;

bool canFormPalindrome(string s)
{
    int odd = 0;

    // Count frequency using two loops
    for (int i = 0; s[i]; i++) {
        int count = 0;

        for (int j = 0; s[j]; j++) {
            if (s[i] == s[j])
                count++;
        }

        if (count % 2 != 0)
            odd++;

        if (odd > 1)
            return false;
    }

    return true;
}

// Driver code 
int main()
{
    cout << (canFormPalindrome("amazon") ? "True\n" : "False\n");
    cout << (canFormPalindrome("carrace") ? "True\n" : "False\n");

    return 0;
}

class GFG {

    static boolean canFormPalindrome(String s)
    {
        int odd = 0;

        // Count frequency using two loops
        for (int i = 0; i < s.length(); i++) {
            int count = 0;

            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j))
                    count++;
            }

            if (count % 2 != 0)
                odd++;

            if (odd > 1)
                return false;
        }

        return true;
    }

    public static void main(String[] args)
    {
        System.out.println(canFormPalindrome("amazon") ? "True" : "False");
        System.out.println(canFormPalindrome("carrace") ? "True" : "False");
    }
}

def canFormPalindrome(s):
    odd = 0

    # Count frequency using two loops
    for i in range(len(s)):
        count = 0

        for j in range(len(s)):
            if s[i] == s[j]:
                count += 1

        if count % 2 != 0:
            odd += 1

        if odd > 1:
            return False

    return True


# Driver code
print("True" if canFormPalindrome("amazon") else "False")
print("True" if canFormPalindrome("carrace") else "False")

using System;

class GFG {

    static bool CanFormPalindrome(string s)
    {
        int odd = 0;

        // Count frequency using two loops
        for (int i = 0; i < s.Length; i++) {
            int count = 0;

            for (int j = 0; j < s.Length; j++) {
                if (s[i] == s[j])
                    count++;
            }

            if (count % 2 != 0)
                odd++;

            if (odd > 1)
                return false;
        }

        return true;
    }

    static void Main(string[] args)
    {
        Console.WriteLine(CanFormPalindrome("amazon") ? "True" : "False");
        Console.WriteLine(CanFormPalindrome("carrace") ? "True" : "False");
    }
}

function canFormPalindrome(s) {
    let odd = 0;

    // Count frequency using two loops
    for (let i = 0; i < s.length; i++) {
        let count = 0;

        for (let j = 0; j < s.length; j++) {
            if (s[i] === s[j])
                count++;
        }

        if (count % 2 !== 0)
            odd++;

        if (odd > 1)
            return false;
    }

    return true;
}

// Driver code
console.log(canFormPalindrome("amazon") ? "True" : "False");
console.log(canFormPalindrome("carrace") ? "True" : "False");

False
True

[Better Approach-1] Using Frequency Count - O(n) Time and O(1) Space

First, traverse the string and store the frequency of each character in a count array. Then, check the count array to see how many characters have odd frequency. If more than one character has an odd count, it is not possible to form a palindrome; otherwise, it is possible.

#include <iostream>
#include <string>
using namespace std;

bool canFormPalindrome(string s)
{
    int count[256] = {0};

    // Count frequency of characters
    for (int i = 0; s[i]; i++)
        count[s[i]]++;

    int odd = 0;

    // Count odd frequencies
    for (int i = 0; i < 256; i++) {
        if (count[i] % 2 != 0)
            odd++;

        if (odd > 1)
            return false;
    }

    return true;
}

// Driver code 
int main()
{
    cout << (canFormPalindrome("amazon") ? "True\n" : "False\n");
    cout << (canFormPalindrome("carrace") ? "True\n" : "False\n");

    return 0;
}

class GFG {

    static boolean canFormPalindrome(String s)
    {
        int[] count = new int[256];

        // frequency count
        for (int i = 0; i < s.length(); i++)
            count[s.charAt(i)]++;

        int odd = 0;

        // check odd frequencies
        for (int i = 0; i < 256; i++) {
            if (count[i] % 2 != 0)
                odd++;

            if (odd > 1)
                return false;
        }

        return true;
    }

    // Driver code
    public static void main(String[] args)
    {
        System.out.println(canFormPalindrome("amazon") ? "True" : "False");
        System.out.println(canFormPalindrome("carrace") ? "True" : "False");
    }
}

def canFormPalindrome(s):
    count = [0] * 256

    # frequency count
    for ch in s:
        count[ord(ch)] += 1

    odd = 0

    # check odd frequencies
    for c in count:
        if c % 2 != 0:
            odd += 1
        if odd > 1:
            return False

    return True


# Driver code
print("True" if canFormPalindrome("amazon") else "False")
print("True" if canFormPalindrome("carrace") else "False")

using System;

class GFG {

    static bool CanFormPalindrome(string s)
    {
        int[] count = new int[256];

        // frequency count
        for (int i = 0; i < s.Length; i++)
            count[s[i]]++;

        int odd = 0;

        // check odd frequencies
        for (int i = 0; i < 256; i++) {
            if (count[i] % 2!= 0)
                odd++;

            if (odd > 1)
                return false;
        }

        return true;
    }

    // Driver code
    static void Main(string[] args)
    {
        Console.WriteLine(CanFormPalindrome("amazon")? "True" : "False");
        Console.WriteLine(CanFormPalindrome("carrace")? "True" : "False");
    }
}

function canFormPalindrome(s) {
    let count = Array(256).fill(0);

    // frequency count
    for (let ch of s) {
        count[ch.charCodeAt(0)] += 1;
    }

    let odd = 0;

    // check odd frequencies
    for (let c of count) {
        if (c % 2!== 0) {
            odd += 1;
        }
        if (odd > 1) {
            return false;
        }
    }

    return true;
}

// Driver code
console.log(canFormPalindrome("amazon") ? "True" : "False");
console.log(canFormPalindrome("carrace")? "True" : "False");

False
True

[Better Approach-2] Using Bit Manipulation (Bitmask) - O(n) Time and O(1) Space

The idea is to track the frequency of characters using a bitmask instead of counting each one separately. If character set is limited (say only lowercase, i.e., 26 characters), a single integer's bits (total 32 bits typically) can be used to track odd frequencies.

For every character in the string, we toggle its corresponding bit (using XOR). If a character appears even number of times, its bit becomes 0; if it appears odd number of times, its bit becomes 1. In the end, we just check the bitmask. If at most one bit is set (i.e., at most one character has odd frequency), then the string can form a palindrome; otherwise, it cannot.

#include <iostream>
#include <string>
using namespace std;

bool canFormPalindrome(string s)
{
    int mask = 0;

    // toggle bits
    for (int i = 0; s[i]; i++) {
        int bit = s[i] - 'a';
        mask ^= (1 << bit);
    }

    // check at most one bit set
    return (mask == 0) || (mask & (mask - 1)) == 0;
}

// Driver code
int main()
{
    cout << (canFormPalindrome("amazon") ? "True\n" : "False\n");
    cout << (canFormPalindrome("carrace") ? "True\n" : "False\n");

    return 0;
}

class GFG {

    static boolean canFormPalindrome(String s)
    {
        int mask = 0;

        // toggle bits
        for (int i = 0; i < s.length(); i++) {
            int bit = s.charAt(i) - 'a';
            mask ^= (1 << bit);
        }

        // check at most one bit set
        return (mask == 0) || ((mask & (mask - 1)) == 0);
    }

    public static void main(String[] args)
    {
        System.out.println(canFormPalindrome("amazon") ? "True" : "False");
        System.out.println(canFormPalindrome("carrace") ? "True" : "False");
    }
}

class GFG:
    @staticmethod
    def canFormPalindrome(s):
        mask = 0

        # toggle bits
        for ch in s:
            bit = ord(ch) - ord('a')
            mask ^= (1 << bit)

        # check at most one bit set
        return mask == 0 or (mask & (mask - 1)) == 0


# Driver code
print("True" if GFG.canFormPalindrome("amazon") else "False")
print("True" if GFG.canFormPalindrome("carrace") else "False")

using System;

class GFG {

    public static bool CanFormPalindrome(string s)
    {
        int mask = 0;

        // toggle bits
        for (int i = 0; i < s.Length; i++) {
            int bit = s[i] - 'a';
            mask ^= (1 << bit);
        }

        // check at most one bit set
        return (mask == 0) || ((mask & (mask - 1)) == 0);
    }

    static void Main(string[] args)
    {
        Console.WriteLine(CanFormPalindrome("amazon") ? "True" : "False");
        Console.WriteLine(CanFormPalindrome("carrace") ? "True" : "False");
    }
}

class GFG {

    static canFormPalindrome(s) {
        let mask = 0;

        // toggle bits
        for (let i = 0; i < s.length; i++) {
            let bit = s.charCodeAt(i) - 'a'.charCodeAt(0);
            mask ^= (1 << bit);
        }

        // check at most one bit set
        return mask === 0 || (mask & (mask - 1)) === 0;
    }
}

// Driver code
console.log(GFG.canFormPalindrome("amazon") ? "True" : "False");
console.log(GFG.canFormPalindrome("carrace") ? "True" : "False");

False
True