All substrings and 'semi-substrings' of a String

Question

I know I can get all the substrings of a given String like this:

String inputString = "abcde";

java.util.Set<String> substrings = new java.util.TreeSet<>();
int strLength = inputString.length();
for(int i=0; i<strLength; i++)
  for(int j=0; j<=strLength-i; j++)
    substrings.add(inputString.substring(i, i+j));

Which will get me the following result in the Set:

a, ab, abc, abcd, abcde, b, bc, bcd, bcde, c, cd, cde, d, de, e, 

However, I want to somehow get the following list instead:

a, ab, abc, abcd, abcde, abce, abd, abde, abe, ac, acd, acde, ace, ad, ade, ae, b, bc, bcd, bcde, bce, bd, bde, be, c, cd, cde, ce, d, de, e

So in addition to all the substrings, I also want the strings when you remove one or multiple characters in between (i.e. ace by removing b and d).

What would be the easiest way to accomplish this?

NOTE: All the characters should remain in the same order, otherwise I would combine all permutations of a string with all substrings of those Strings.

Answer 1

Check this solution out. My instructor in my software engineering class provided us with this solution a while back. I edited it a bit to make sure you get an ordered set with TreeSet.

public static Set<String> stringSubsets(String str) {
    if (str.isEmpty()) {
        return new TreeSet<>(Arrays.asList(""));
    } else {
        char currentChar = str.charAt(0);
        String rest = str.substring(1);

        Set<String> combinationsOfRest = stringSubsets(rest);
        Set<String> result = new TreeSet<>();

        result.addAll(combinationsOfRest);
        for (String c: combinationsOfRest)
            result.add(currentChar + c);

        return result;
    }
}