Finding variants of a string (only deletion, no transposition)

Question

Given a string, I want to find all variants without transposition, only deletion. For example, given the string:

helloo

The list of variants would be as follows (separated by white space).

helloo hello heloo helo

My solution so far is to move through each character, and then if the current character matches the next character, recursively try the original and the deleted character version, as follows.

// takes String with at most two consecutive characters of any character, 
// and returns an Iterable of all possible variants (e.g. hheello -> heello, hhello, ...)
private static Iterable<String> findAllVariants(String word) {
    StringBuilder variant = new StringBuilder(word);
    Queue<String> q = new LinkedList<String>();
    findAllVariants(word, variant, 0, q);
    return q;
}

// helper method
private static void findAllVariants(String word, StringBuilder variant, int currIndex, Queue<String> q) {
    if (currIndex == variant.length() - 1) q.add(variant.toString());

    for (int i = currIndex; i < variant.length() - 1; i++) {
        char thisChar = variant.charAt(i);
        char nextChar = variant.charAt(i+1);
        if (thisChar == nextChar) {
            // get all variants with repeat character
            findAllVariants(word, variant, i+1, q);

            // get all variants without repeat character;
            variant = variant.deleteCharAt(i);
            findAllVariants(word, variant, i, q);
        }
    }
}

However, I end up getting a large number of copies of answers, and none of others. When I do my algorithm on paper, it seems correct. What am I doing wrong?

Answer 1

Something along the lines of the following code will enable you to get all possibilities (remember to add word itself if needed). The idea is to retreive all possibilities for removing one char (e.g. hello results in ello hllo helo hell). These results can in turn be used to get the possibilities for removing two chars (remove one char again). Resulting in llo elo ell for ello and so on...

List<String> getPossibilities(String word) {
    int removeChars = word.length() - 1;
    List<String> possibilities = new ArrayList();
    List<String> options = Arrays.asList(word);
    for(int i = 0; i <= removeChars; i++) {
        List<String> results = new ArrayList();
        for(String option : options) {
          for(String result : removeOneChar(option)) {
                if(!results.contains(result)) {
                    results.add(result);
                }
            }
        }
        possibilities.addAll(results);
        options = results;
    }
    return possibilities;
}

private static List<String> removeOneChar(String word) {
    List<String> results = new ArrayList();
    for(int i = 0; i < word.length(); i++) {
        int secondPart = i + 2;
        if(secondPart <= word.length()) {
            results.add(
                    word.substring(0, i) 
                    + word.substring(i + 1, word.length()));
        }
        else {
            results.add(
                    word.substring(0, i));
        }
    }
    return results;
}

Notice the if(!contains(result)) in order to prevent any duplicates.

Note I've used substring() to accomplish this, you're approach with removeCharAt() is a another good option. You could run some tests to see which performs better to decide which one to use. Notice using the latter could possibly remove the need of the if in the private method.

Answer 2

I'd use rather different algorithm: I'd find all repetitions (ll) (oo) (lll) (ooo) etc.., keep an array describing their positions in the text, and the count of characters per each repetition.
e.g Array A =
[l|2]
[o|2]
.
.
.

Then I'd say have second array with initial count zero and increase there the count and print out all permutations:

Array B =
[l|1]
[o|1]
==> prints helo

Step 2: (increment count)
B =
[l|2]
[o|1]
==> prints hello

Step 3:
B =
[l|3] ==> bigger than max,so reset it to 0, and increment the second cell now, so it becomes:
B =
[l|1]
[o|2]
==> prints heloo

Step 4: (increment first elem again)
[l|2] ==> not bigger than max, so no overflow, so keeping it that way
[o|2]
==> prints helloo