C# BitArray O(n) time complexity, O(1) space


  • 2
    I

    There is no more than 1 character appears odd times in string, then its permutation can form a palindrome

    public bool CanPermutePalindrome(string s) {
                    BitArray ba = new BitArray(256);
                    int count = 0; // count how many characters appear odd time
                    foreach (char c in s)
                    {
                        ba[c] = !ba[c];  // flip bit
                        if (ba[c]) count++;  // 1,  increase count
                        else       count--;    //  0, decrease count
                    }
                        
                    return count < 2; 
            }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.