Post
Ask Question

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: ");  
  6.         var firstInputString = Console.ReadLine();  
  7.   
  8.         Console.Write("Please enter second string to be processed: ");  
  9.         var secondInputString = Console.ReadLine();  
  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.   
  18.         Console.ReadLine();  
  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.


Similar Articles