# String Algorithm - Check String Permutation

## Problem Statement

Write a program to validate if two given strings are a permutation-combination of each other. You need to consider that the comparison is case sensitive and whitespace is significant

Example 1

Input - s1 = "bat" s2 = "tab"
Output - True
Explanation - s2 is a permutation of s1("bat").

Example 2

Input - s1 = "God" s2 = "doG"
Output - True
Explanation - s2 is a permutation of s1("God").

Example 3

Input - s1 = "bat" s2 = "Tab"
Output - True
Explanation - s2 is not a permutation of s1("bat") because s2 contains ‘T’ in lowercase whereas s1 contains ‘t’ in lowercase.

Example 4

Input - s1 = "abc" s2 = "abcd"
Output - True
Explanation - s2 is not a permutation of s1("abcd") because s2 contains 4 characters whereas s1 contains 3 characters.

## Solution

As per the definition of permutation, we know they have the same characters but in different orders. So, let’s have a look at the steps described for an algorithm.

Compare the length of both the strings. If they do not match, then it concludes that the given strings are not in a permutation. Print the result and exit the program; else continue with the following steps.
• Convert both the given strings into an array of type character.
• Declare an array of integer type with size 128 that maps the ASCII value because as per the ASCII standard character set, there are 128 characters for electronic communication.
• Iterate through the first array and for the index matching with the character ASCII value, set the value in the integer array to 1 if the value is 0 OR set the value in the integer array to 0 if the value is 1.
• Iterate through the second array and for the index matching with the character ASCII value, set the value in the integer array to 1 if the value is 0 OR set the value in the integer array to 0 if the value is 1
After iterating over both the arrays, the resultant value in the integer for each of the indices should be 0. In case we see any index with odd value, i.e., 1, then it concludes that the given strings are not permutations.
1. class Program
2. {
3.     static void Main(string[] args)
4.     {
5.         Console.Write("Please enter first string to be processed: ");
7.
8.         Console.Write("Please enter second string to be processed: ");
10.
11.         if (!string.IsNullOrWhiteSpace(firstInputString) && !string.IsNullOrWhiteSpace(secondInputString))
12.         {
13.             //assumption : comparison is case sensitive and whitespace is significant
14.             Console.WriteLine(IsPermutation(firstInputString, secondInputString) ? "Given strings are permutation of each other"
15.                 : "Given strings are not permutation of each other");
16.         }
17.
19.     }
20.
21.     private static bool IsPermutation(string firstInputString, string secondInputString)
22.     {
23.         //Compare Length of two strings, if they do not match then it concludes that the given strings are not permutation
24.         if (firstInputString.Length != secondInputString.Length)
25.         {
26.             return false;
27.         }
28.
29.         //Convert string into an array
30.         char[] firstInputStringCharacterSet = firstInputString.ToCharArray();
31.         char[] secondInputStringCharacterSet = secondInputString.ToCharArray();
32.         //declare an array of integer type with size 128 because as per the ASCII standard character set
33.         //there are 128 characters for electronic communication.
34.         int[] characterSetMappingTable = new int[128];
35.
36.         //Iterate through first array and for the index matching with the character ASCII value,
37.         //set the value in the integer array to 1 if the value is 0 OR set the value in the integer array to 0 if the value is 1
38.         PrepareCharacterSetMappingTable(firstInputStringCharacterSet, characterSetMappingTable);
39.         //Iterate through second array and for the index matching with the character ASCII value,
40.         //set the value in the integer array to 1 if the value is 0 OR set the value in the integer array to 0 if the value is 1
41.         PrepareCharacterSetMappingTable(secondInputStringCharacterSet, characterSetMappingTable);
42.
43.         //After iterating over both the arrays, the resultant value in the integer array for each of the index should be 0.
44.         //In case we see any index with odd value i.e., i then it concludes that the given strings are not permutation.
45.
46.         return IsOddOneFound(characterSetMappingTable);
47.     }
48.
49.     private static void PrepareCharacterSetMappingTable(char[] inputStringCharacterSet, int[] characterSetMappingTable)
50.     {
51.         foreach (char inputStringCharacter in inputStringCharacterSet)
52.         {
53.             var characterIndex = (int)inputStringCharacter;
54.
55.             switch (characterSetMappingTable[characterIndex])
56.             {
57.                 case 0:
58.                     characterSetMappingTable[characterIndex] = 1;
59.                     break;
60.                 case 1:
61.                     characterSetMappingTable[characterIndex] = 0;
62.                     break;
63.             }
64.         }
65.     }
66.
67.     /// <summary>
68.     /// Check if any index contains odd value in the integer array or not
69.     /// </summary>
70.     /// <param name="characterSetMappingTable">array of integer type with size 128 </param>
71.     /// <returns></returns>
72.     private static bool IsOddOneFound(int[] characterSetMappingTable)
73.     {
74.         return characterSetMappingTable.All(index => index != 1);
75.     }
76. }

## Time Complexity

O(n + n + 128) which is same as O(n).

Let me explain how this is calculated. The first array iteration takes O(n) time to iterate through n characters where n is the length of the string. Similarly, the second array iteration also takes O(n) time to iterate through n characters where n is the length of the string. Finally, iterate through the results to validate if any index contains an odd value in the integer array takes O(128) – a constant time.

Please feel free to propose or suggest a solution you think can be followed to make it better and more optimized.