Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. String

Palindrome Permutation

String, Bits Approach

You are given a string 'S', check if there exists any permutation of the given string that is a palindrome.

  • A palindrome is a word or phrase that reads the same from forward and backward e.g. “aba”, it reads the same from forward and backward.

  • A permutation is a rearrangement of letters.

  • The palindrome does not need to be limited to just dictionary words.

Solutions

A palindrome is a string that is the same forwards and backwards. Therefore, to decide if a string is a permutation of a palindrome, we need to know if it can be written such that it's the same forwards and backwards.

What does it take to be able to write a set of characters the same way forwards and backwards? We need to have an even number of almost all characters, so that half can be on one side and half can be on the other side. At most one character (the middle character) can have an odd count.

For example, we know tactcoapapa is a permutation of a palindrome because it has two Ts, four As, two Cs, two Ps, and one 0. That O would be the center of all possible palindromes.

Approach – Using hash table

Implementing this algorithm is fairly straightforward. We use a hash table to count how many times each character appears. Then, we iterate through the hash table and ensure that no more than one character has an odd count.

Steps

  1. First check if string is null. if string is null, then return string.

  2. Run loop for each character of string and add it's count into hash table and count odd occurrence ( count % 2 == 1).

  3. If odd occurrence is less than and equal to one, then string is palindrome else not.

   public bool IsPermutationOfPalindrome(string str)
    {
        if (str is null)
            return true;

        int countOdd = 0;
        var table = new Dictionary<int, int>();
        foreach (char item in str!)
        {
            int x = Char.ToLower(item);
            if (!table.ContainsKey(x))
            {
                table.Add(x, 1);
            }
            else
            {
                table[x]++;
            }

            if (table[x] % 2 == 1)
            {
                countOdd++;

            }
            else
            {
                countOdd--;
            }
        }
        return countOdd <= 1;
    }

Note: Here, we made all character to lower case to make it case insensitive.

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(n)

Approach – Using bit vector

If you think more deeply about this problem, you might notice that we don't actually need to know the counts. We just need to know if the count is even or odd. Think about flipping a light on/off (that is initially off). If the light winds up in the off state, we don't know how many times we flipped it, but we do know it was an even count.

Given this, we can use a single integer (as a bit vector). When we see a letter, we map it to an integer between O and 26 (assuming an English alphabet). Then we toggle the bit at that value. At the end of the iteration, we check that at most one bit in the integer is set to 1.

We can easily check that no bits in the integer are 1: just compare the integer to 0. There is actually a very elegant way to check that an integer has exactly one bit set to 1.

An integer like 00010000. We could of course shift the integer repeatedly to check that there's only a single 1. Alternatively, if we subtract 1 from the number, we'll get 00001111. What's notable about this is that there is no overlap between the numbers (as opposed to say 00101000, which, when we subtract 1 from, we get 00100111.) So, we can check to see that a number has exactly one 1 because if we subtract 1 from it and then AND it with the new number, we should get 0.

Steps

  1. First check if string is null. if string is null, then return string.

  2. Run loop for each character of string and add toggle each bit.

  3. Check bit vector value is zero or bitwise and of bit vector with subtract one from bit vector is zero.

   public bool IsPermutationOfPalindrome(string str)
    {
        int bitVactor = CreateBitVactor(str);

        return bitVactor == 0 || (bitVactor & (bitVactor - 1)) == 0;
    }

    private int CreateBitVactor(string str)
    {
        int bitVactor = 0;
        foreach (char item in str)
        {
            bitVactor = Toggle(bitVactor, item);
        }
        return bitVactor;
    }
    private int Toggle(int bitVactor, int index)
    {
        if (index < 0)
        {
            return bitVactor;
        }

        int mask = 1 << index;

        if ((bitVactor & mask) == 0)
        {
            bitVactor |= mask;
        }
        else
        {
            bitVactor &= ~mask;
        }
        return bitVactor;
    }

Complexity

  • Time Complexity: O(n)

  • Auxiliary Space: O(1)

PreviousString CompressionNextDetermine if a string has all Unique Characters

Last updated 1 year ago

image