Making as many unique strings as possible by removing two characters I'm attempting a programming challenge type task in C#, where the goal is to determine how many unique strings can be obtained by removing two characters. The prompt for the task implied that I should create the set of all possible strings with 2 chars removed, then return the number of items in the set. I was initially suspicious of this, as I've often found that the only way to complete these kinds of tasks is to abstract away from actually storing results or enumerating possibilities wherever possible - but due to the requirement that only unique strings should be counted, I don't know how to avoid storing information about every result so far. Supposedly I have to be able to handle strings of up to a million characters in length - and I can't think of any way right now to avoid the hideous iteration count and massive result set that a million character string would require.
Here is my code so far. It works, but its way too slow, and I think large inputs might be generating incorrect results, but I'm not actually sure:
 private static void Main(String[] args)
{
    var input = Console.ReadLine();
    Console.WriteLine(FindBeautifulStrings(input).Count);
}

// B will always be larger than A because of the way we're iterating so we have to remove it first.
private static string RemoveTwo(string input, int indexA, int indexB)
{
    return input.Remove(indexB, 1).Remove(indexA, 1);
}

private static HashSet&lt;int&gt; FindBeautifulStrings(string input)
{
    // Iterate over every character in the string, then for each character, iterate over every
    // other character, removing the two selected characters; return set of all possible results.
    int inputLength = input.Length;
    HashSet&lt;int&gt; results = new HashSet&lt;int&gt;();
    for (int i = 0; i &lt; inputLength; ++i)
    {
        for (int j = i + 1; j &lt; inputLength; ++j)
        {
            results.Add(RemoveTwo(input, i, j).GetHashCode());
        }
    }
    return results;
}

Storing hashes of strings instead of strings themselves is the only idea I've come up with in terms of more efficiently detecting a string identical to one I've already seen. Since the non-duplicate requirement means that the resulting combinations themselves are significant, I haven't been able to avoid working with strings entirely and solve it mathematically instead (if duplicates were permissable, I feel like this could be solved using the equation n!/(n - (n - 2)! * (n - 2)!. Is there any way to determine the non-duplicate possibilities mathematically without iterating over or storing the strings themselves? If not, is there any way to optimise what I have so far?
Edit:
I thought I should clarify - although the question intuitively feels like it's about permutations, a mistake made both by myself initially and by a few others so far, the only operation performed on the original string is removal of characters.
It works, I think, like this:
input: apple

i=0, j=1: ple
i=0, j=2: ple **Doesn't count, duplicate**
i=0, j=3: ppe
i=0, j=4: ppl
i=1, j=2: ale
i=1, j=3: ape
i=1, j=4: apl
i=2, j=3: ape **Doesn't count, duplicate**
i=2, j=4: apl **Doesn't count, duplicate**
i=3, j=4: app

Unique strings: 7
Instead of using string.Remove (and creating a 2 string for each index combination), you could create an array of chars / ints and work on that array.
You dont have to iterate from i = 0 to i = str.Length and j = 0 to j.str.Length because that results in duplicated indexes (e.g. 1,2 and 2,1).
The idea with the hashes is good, but as mentioned in comment, you have to check for all "uncertain duplicates" if they are actually duplicates.


The following code shows a simple implementaion that considers the points above:

public class Variation
{
    public Variation(int hash, int index1, int index2)
    {
        Hash = hash;
        Index1 = index1;
        Index2 = index2;
    }
    public int Index1 { get; }
    public int Index2 { get; }
    public int Hash { get; }
}

public int CountVariantions(string input)
{
    int[] inputArray = input.ToCharArray().Select(c =&gt; (int)c).ToArray();
    var variations = new List&lt;Variation&gt;();
    for (int i = 0; i &lt; input.Length; i++)
        for (int j = i + 1; j &lt; input.Length; j++)
            variations.Add(GetVariation(inputArray, i, j));

    var groups = variations.GroupBy(v =&gt; v.Hash).ToArray();

    var uncertainDublicates = groups.Where(g =&gt; g.Skip(1).Any()).ToArray();

    var dublicatesRealCount = GetRealCount(inputArray, uncertainDublicates);

    return groups.Length - uncertainDublicates.Length + dublicatesRealCount;
}

private int GetRealCount(int[] inputArray, IEnumerable&lt;IGrouping&lt;int, Variation&gt;&gt; duplicates)
{
    // todo: check if the duplicates are actually identically
    return duplicates.Count();
}

private static Variation GetVariation(int[] inputArray, int index1, int index2)
{
    var hashValue = Enumerable
        .Range(0, inputArray.Length)
        .Where(i =&gt; i != index1 &amp;&amp; i != index2)
        .Select(i =&gt; inputArray[i])
        .Aggregate((hash, val) =&gt; hash ^ val);

    return new Variation(hashValue, index1, index2);
}