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

Check if two strings are permutation of each other

String, Iterative approach

Write a function to check whether two given strings are Permutation of each other or not. A Permutation of a string is another string that contains same characters, only the order of characters can be different. For example, “abcd” and “dabc” are Permutation of each other.

Solutions

Like in many questions, we should confirm some details with our interviewer. We should understand if the permutation comparison is case sensitive. That is: is God a permutation of dog? Additionally, we should ask if whitespace is significant. We will assume for this problem that the comparison is case sensitive and whitespace is significant. So, "god " is different from "dog".

Approach – Sort the strings

If two strings are permutations, then we know they have the same characters, but in different orders. Therefore, sorting the strings will put the characters from two permutations in the same order. We just need to compare the sorted versions of the strings.

Note: Please note that the program is case-sensitive.

Steps

  1. First check if any string is null. If both null, then return true else any one is null then return false.

  2. Check the length of string. If length is different, then return false.

  3. Sort both strings alphabetically.

  4. Run a loop till length on any string and compare each character of both strings index wise.

     public bool ArePermutation(string str1, string str2)
    {
        if (str1 is null && str2 is null)
            return true;

        if (str1?.Length != str2?.Length)
            return false;

        var char1 = str1!.ToArray();
        var char2 = str2!.ToArray();

        Array.Sort(char1);
        Array.Sort(char2);

        for (int i = 0; i < str1!.Length; i++)
            if (char1[i] != char2[i])
                return false;

        return true;
    }

Complexity

  • Time complexity: O(N log N)

  • Space complexity: O(1)

Approach – Check if the two strings have identical character counts

We can also use the definition of a permutation-two words with the same character counts-to implement this algorithm.

Note: Please note that the program is case-sensitive.

Steps

  1. First check if any string is null. If both null, then return true else any one is null then return false.

  2. Check the length of string. If length is different, then return false.

  3. Create an integer array of ASCII characters length (256).

  4. Run a loop till length on any string.

  5. Get character from first string and increase that number count and get character from second string and decrease that number count.

  6. Run a loop till length of an integer array and check if any number count is not equal to zero. If any number count is not zero, then return false else true.

   public bool ArePermutation(string str1, string str2)
    {
        int NO_OF_CHARS = 256;
        if (str1 is null && str2 is null)
            return true;

        if (str1?.Length != str2?.Length)
            return false;

        var temp = new int[NO_OF_CHARS];

        for (int i = 0; i < str1!.Length; i++)
        {
            temp[str1![i]]++;
            temp[str2![i]]--;
        }

        for (int i = 0; i < temp.Length; i++)
        {
            if (temp[i] != 0)
                return false;
        }
        return true;
    }

Complexity

  • Time complexity: O(N)

  • Space complexity: O(N)

PreviousStringNextString Compression

Last updated 1 year ago