Making as many unique strings as possible by removing two characters
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);
}