Determine if two strings with no repeating characters are permutations of each other

I've made a short program to determine if a string is permutation of another string.

Example input/output :

a) 123, 112 <- False

b) 123, 321 <- True

c) 112, 121 <- these don't count as permutations since they have duplicate characters

    private static void Main()
{
Console.WriteLine(IsPermutation(a, b));
}

private static bool IsPermutation(string first, string second)
{
if (first.Length != second.Length)
{
return false;
}
for (int i = 0; i < first.Length; i++)
{
if (first.Count(t => t == second[i]) != second.Count(t => t == first[i]))
{
return false;
}
}
return true;
}


I wonder if it can be optimized.

• It is unclear what you mean by "permutation of another string". Please add a thorough explanation, as well as examples to illustrate what is or isn't a "permutation". Commented Dec 8, 2016 at 0:09
• I've updated the question. Commented Dec 8, 2016 at 0:15

This can almost certainly be optimized. Look at your algorithm:

1. Take the next character from the first string
2. Count all instances of that character in the both strings by iterating over them.
3. Compare the count of the character in each string.

Now, let's look at how many times you iterate the strings: The first string is iterated N * N times, and the second string is iterated N * N times, where N is the count of the characters in the string. This makes 2N^2 iterations. It would probably be much faster (depending on the string length) to split these strings into character arrays, sort each of the arrays, and do an iteration like this:

list1 = Array.Sort(first.ToCharArray());
list2 = Array.Sort(second.ToCharArray());

for (var i = 0; i < list1.Count; i++)
{
if (list1[i] != list2[i])
{
return false;
}
}

return true;


Update:

I misunderstood what your program was meant to do the first time around.

First, you should understand that a permutation is:

Permutation: A way, especially one of several possible variations, in which a set or number of things can be ordered or arranged.

At first, I didn't understand that duplicate items within the string were not allowed.

Second, your program does not work correctly. Consider the following strings: "13234" and "43231". Your program will return true for these values because the "3"s are in the same indexes in the string, and therefore the count for each item at the index matches. "123344" and "124433" also return true because you only check that the items in the same index in each string have the same count.

To correctly handle this with your method, you would need to first compare the strings and return true for duplicate values (e.g. "1233" is considered a "permutation" of "1233"). Then, you would need to check that the count of each item in the string is 1 and that each item is in the other string.

If I were to implement this program, I would do it as Paparazzi suggested, except I would check that each item is not already in the dictionary as I do the first iteration to prevent duplicates in the first string and ensure that the value is 1 every time I try to remove an item to prevent duplicates in the second string.

If you were sure that each string as no duplicates, you could use Dmitry's method, but you clearly do not expect each string to contain no duplicates because you attempted to rule out duplicates in your first solution.

• That's not correct just try 123 and 321 as input Commented Dec 7, 2016 at 22:07
• I edited it to show the sorting part, instead of just the comparison part. Is it clearer now?
– user34073
Commented Dec 7, 2016 at 22:13
• And yes, my solution will work for inputs of "123" and "321".
– user34073
Commented Dec 7, 2016 at 22:14
• Yes you've made it clearer now it works just fine Commented Dec 7, 2016 at 22:20
• Sort is on average is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation. Commented Dec 7, 2016 at 23:15

You could use the SetEqual<T> helper method from this answer.
It uses a dictionary as follows:

1. The dictionary is filled with the items of the first collection and with their number of occurences.
2. Number of occurences is decreased for each item in the second collection.

Thus your method can be rewritten as:

private static bool IsPermutation(string first, string second)
{
if (first.Length != second.Length)
{
return false;
}
return SetEqual(first, second);
}


If you are sure that strings contain only unique chars, there is a more efficient approach using the HashSet<T>:

private static bool IsPermutation(string first, string second)
{
if (first.Length != second.Length)
{
return false;
}
HashSet<char> chars = new HashSet<char>(first);
return second.All(chars.Contains);
}

• Those are variations not permutations. Commented Dec 7, 2016 at 22:41
• @denis My English isn't good enough so please point me to the difference. Commented Dec 7, 2016 at 22:44
• the permutations of 123 are (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1) while the variations are all of the above but they include (1,1,1), (1,1,2), and so on.. the difference is that permutations don't have repetitive characters. Commented Dec 7, 2016 at 22:49
• @denis Do you mean we cannot say that (1,2,1) is a permutation of (1,1,2)? Commented Dec 7, 2016 at 22:56
• @denis it's not quite clear whether you're permuting tuples (which allow duplicates) or sets (which don't do so) ... could you clarify a bit? because strings in general are basically tuples. Commented Dec 7, 2016 at 23:04

I think this is going to be O(n) as Dictionary Add and Lookup are O(1)

private static bool IsPermutation(string first, string second)
{
if (first.Length != second.Length)
return false;
if (first.Length == 0)
return false;
Dictionary<char, int> countEm = new Dictionary<char, int>(first.Length);
foreach (char c in first)
{
if (countEm.Keys.Contains(c))
countEm[c]++;
else
}
foreach (char c in second)
{
if (countEm.Keys.Contains(c))
{
if (countEm[c] == 0)
return false;
countEm[c]--;
}
else
return false;
}
return true;
}

• Isn't this the same approach as in my answer? Commented Dec 7, 2016 at 23:25
• It is similar but I think it is more efficient. I did not look to your link before writing this. Commented Dec 7, 2016 at 23:38
• @denis I think you were a little quick to accept an answer. Commented Dec 7, 2016 at 23:40
• @denis Uh, even the accepted answer said this is probably faster. Commented Dec 8, 2016 at 0:07
• People often forget the notion of big O notation. The dictionary contains is indeed O(1) but that does not mean that this algorithm will be faster everytime comparing to the sorting approach. Using an auxiliary lookup will occur to a significant overhead, that's why the sorted algorithm might be faster on some scenarios. The size of first needs to be very big to see the gain with this approach. It would be interesting to see an array in action instead of a dictionary. After all there are only 26 English letters (52, if you are case sensitive). That dismisses other letters though. Commented Dec 8, 2016 at 16:40