4
\$\begingroup\$

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<int> 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<int> results = new HashSet<int>();
    for (int i = 0; i < inputLength; ++i)
    {
        for (int j = i + 1; j < 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
\$\endgroup\$
  • \$\begingroup\$ I considered parallelising the operations, which would reduce overall execution time - however it won't help solve the problem in the context of this challenge, as the execution time for the purposes of passing or failing is the sum of the execution time of all threads. \$\endgroup\$ – Toadfish Jun 13 '16 at 8:54
  • 1
    \$\begingroup\$ This sounds like what you're after: cs.stackexchange.com/q/2443 \$\endgroup\$ – forsvarir Jun 13 '16 at 9:05
  • \$\begingroup\$ @forsvarir it does seem similar, however the problem I'm working on doesn't seem to be a typical permutation/combination problem, since the string is never re-arranged, only changed by deleting any two elements. \$\endgroup\$ – Toadfish Jun 13 '16 at 9:11
  • 2
    \$\begingroup\$ If the hash values of 2 string are identical does not mean that the strings are also identical, so you algorithm above is not dependably. \$\endgroup\$ – JanDotNet Jun 13 '16 at 9:43
  • 2
    \$\begingroup\$ Let s1 be the string generated by deleting characters at indices a1 and b1, and s2, a2, b2 similarly. Obviously they have the same prefix up to min(a1,a2) and the same suffix after max(b1,b2), so they are equal iff the middle range is equal. By case-splitting on the possible orders (e.g. a1 < a2 < b2 < b1 is one possible order) you should be able to derive conditions which require repetitions of a single character. Then you try to work back from those conditions to a combinatorial expression in terms of the run-length encoding of the original string. \$\endgroup\$ – Peter Taylor Jun 13 '16 at 10:02
3
\$\begingroup\$
  • 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 => (int)c).ToArray();
    var variations = new List<Variation>();
    for (int i = 0; i < input.Length; i++)
        for (int j = i + 1; j < input.Length; j++)
            variations.Add(GetVariation(inputArray, i, j));

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

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

    var dublicatesRealCount = GetRealCount(inputArray, uncertainDublicates);

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

private int GetRealCount(int[] inputArray, IEnumerable<IGrouping<int, Variation>> 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 => i != index1 && i != index2)
        .Select(i => inputArray[i])
        .Aggregate((hash, val) => hash ^ val);

    return new Variation(hashValue, index1, index2);
}
\$\endgroup\$
3
\$\begingroup\$

For the same problem but with a single deletion, it's easy: for every run of k consecutive characters, you have k identical strings, so you discount k - 1 of them. There are N possible deletions, so the number of distinct strings is N - sum_k k-1.

With two deletions, there are various cases to consider.

  • The first easy case is that for every run of k > 2 identical characters, deleting any two of those characters gives the same result, so of the k(k-1)/2 pairs you can discount k(k-1)/2 - 1 of them.
  • The second easy case is that for every two separate runs of j and k identical characters respectively, there are jk identical strings, so you discount jk - 1 of them.
  • The complicated case is where deleting a character merges two runs. In exponential (run-length encoded) notation we have a substring x^j y x^k and deleting the y gives j + k possibilities for the second deletion which will give the same string, so you discount j + k - 1 of them.
    • Consider substrings of the form xyxy, which have 6 pairs of indices and 4 distinct results, because there are three ways of getting xy. We've discounted one for the xyx and one for the yxy, so we don't need to do any extra processing.

If you first transform the string into a run-length encoded representation then these cases are all pretty simple to check.

\$\endgroup\$
2
\$\begingroup\$

I'm not seeing the need to keep the string characters in order in the requirements you list (though you refer to this in a comment?). If the string is "toenail", but "toena" is as legitimate as "aneot", than what you're after is indeed a permutation - especially if you don't care what the strings are, only the counts.

The number of unique permutations for a given set of characters is:

$$ \dfrac{n!}{(n-r)!\cdot n_1!\cdot n_2!\dots n_x!}$$

... where \$ n \$ is the number of characters in the string, \$ r \$ is the number of characters you want to use. To eliminate duplicates, you need to also divide by the factorials of counts of any duplicates.

So for the word bookkeeper, you have 10 characters, but there are two O's, two K's, and three E's. for unique permutations of 8 characters, the formula is:

$$ \dfrac{10!}{(10-8)!\cdot 2!\cdot 2!\cdot 3!} = 75,600 $$

It's kind of annoying to have to track the counts of each letter, but I don't see any way around that. You could get fancy with linq to query the letters and their counts, or many other options. But that's the heart of it.

The closest link I can find to document this is here. The yellow-highlighted text with the big arrow pointing to it is the key.

\$\endgroup\$
  • \$\begingroup\$ The statement of the requirement is "how many unique strings can be obtained". A string is an ordered list of characters, not a multiset, so this doesn't answer the question. \$\endgroup\$ – Peter Taylor Jun 13 '16 at 15:48
  • \$\begingroup\$ Yes, as much as I want to just treat it as a set problem, it's the fact that they must be considered as ordered strings that seems to force me to actually hold onto every subset to check for duplicates. \$\endgroup\$ – Toadfish Jun 13 '16 at 16:24
  • 1
    \$\begingroup\$ But again, "ordered" isn't the same as "order they were typed". It's true my answer still needs modified to handle the fact that for "bookkeeper", the string "bok" should only be counted once, even though it can be built four different ways given two O's and two K's. I just haven't had time to update it, yet :( If you're truly saying that "obk" is considered an invalid string for the answer because the letters don't appear in the same order as in the original word (I'm skeptical :) it can still be done with sets... I'll try to include that answer, as well. \$\endgroup\$ – James King Jun 13 '16 at 19:16
  • \$\begingroup\$ (I know the answer, the delay is figuring out how to type it in mathematical HTML script, since syb0rg updated my answer to use that) :P #gratefulthough \$\endgroup\$ – James King Jun 13 '16 at 19:21
  • 1
    \$\begingroup\$ I'll quote the rest of that sentence: "obtained by removing two characters". Not "by removing two characters and rearranging the ones which remain". \$\endgroup\$ – Peter Taylor Jun 13 '16 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.