How do I get not just all substrings, but all POSSIBLE substrings of a string?

Question

I have the following code :

public class Application {

public static void main(String[] args)
{
    String source = "Testing";
    go(source);
}

public static void go(String source)
{
    for (int i = 0; i < source.length(); i ++)
    {
        for (int j = i + 1; j <= source.length(); j++)
        {
            System.out.println(source.substring(i, j));
        }
    }
}

}

When I run this code, I get the following output :

T
Te
Tes
Test
Testi
Testin
Testing
e
es
est
esti
estin
esting
s
st
sti
stin
sting
t
ti
tin
ting
i
in
ing
n
ng
g

Which is great and all - But it isn't actually what I want. I would also like to be able to get all the possible strings that are substrings of this word.

Such as gist, set, tie etc.

I realise how my code is wrong for this, but I am also unsure of how I might expand it out to achieve what I want!

Any help is appreciated!

You want all possible permutations of all possible random selections of characters from the string? (gist, set, tie are not even permutations of substrings) — engineerC, Aug 04 '15 at 18:33
Gist, set, tie etc are not substrings of "Testing". They are substrings of some permutations of "Testing". Do you want all possible substrings of all permutations of the given word? That will be a whole lot of strings! 141120 strings for the word "Testing", if my quick calculation was correct (counting duplicates). — marstran, Aug 04 '15 at 18:36
All possible permutations - Just reading your reply below now :) — Slippy, Aug 04 '15 at 21:21
@marstran I get 13700, actually measuring the generated sequence's length. — Will Ness, Aug 04 '15 at 22:12
@WillNess I got that too. My quick calculation was without the `distinct` clause. — marstran, Aug 05 '15 at 06:26

Jegg · Answer 1 · 2015-08-04T18:58:53.773

Try this: not very efficient, but seems work

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class MainClass {

    private static Set<String> store = new HashSet<String>();

    public static void main(String args[]) {

        doAll("testi");

        Iterator<String> it = store.iterator();

        while (it.hasNext()) {

            System.out.println(it.next());

        }

    }

    public static void doAll(String str) {

        for (int i = 0; i < str.length(); i++) {

            String doingString = str.substring(i, str.length());
            permuteString("", doingString);

        }

    }

    public static void permuteString(String beginningString, String endingString) {

        if (endingString.length() <= 1) {


            store.add(beginningString + endingString);
            doAll(beginningString);
        }

        else
            for (int i = 0; i < endingString.length(); i++) {
                try {
                    String newString = endingString.substring(0, i)
                            + endingString.substring(i + 1);

                    permuteString(beginningString + endingString.charAt(i),
                            newString);
                } catch (StringIndexOutOfBoundsException exception) {
                    exception.printStackTrace();
                }
            }
    }
}

score 0 · Answer 2 · answered Aug 04 '15 at 18:47

0

You want all the permutations of all the subsets of characters.

Using Guava:

Set<Character> chars = Sets.newHashSet(Chars.asList(source.toCharArray()));
Set<String> r = Sets.powerSet(chars).stream()
                    .flatMap(cs -> Collections2.permutations(cs).stream()
                                     .map(l -> String.valueOf(Chars.toArray(l))))
                    .collect(Collectors.toSet());

answered Aug 04 '15 at 18:47

Jean Logeart

52,687
11
83
118

Looks nice, but you are removing duplicate characters by using a set though. – marstran Aug 04 '15 at 18:56
True, maybe an other library is better suited for that work then – Jean Logeart Aug 04 '15 at 18:59
Guava has a MultiSet too though. Maybe that can be used? – marstran Aug 04 '15 at 19:22

score 0 · Accepted Answer · edited May 23 '17 at 12:06

By having this permutations function (taken from Generating all permutations of a given string):

public static List<String> permutation(final String str) {
    return permutation("", str);
}

private static List<String> permutation(final String prefix, final String str) {
    final List<String> list = new ArrayList<>();

    final int n = str.length();
    if (n == 0) {
        list.add(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            list.addAll(permutation(prefix + str.charAt(i),
                                    str.substring(0, i) + str.substring(i + 1, n)));
        }
    }

    return list;
}

And this substring function (just changed the return type of your function):

public static List<String> substrings(final String source) {
    final List<String> list = new ArrayList<>();
    for (int i = 0; i < source.length(); i++) {
        for (int j = i + 1; j <= source.length(); j++) {
            list.add(source.substring(i, j));
        }
    }
    return list;
}

I made this solution using Java 8 streams:

public static void main(String[] args) {
    Stream.of("Testing")
          .flatMap(s -> permutation(s).stream())
          .flatMap(s -> substrings(s).stream())
          .distinct()
          .forEach(System.out::println);
}

I wish I understood this solution! It works, but I can't really see why, I don't get what we need a prefix for... — Slippy, Aug 05 '15 at 17:33
@Slippy The prefix is just needed while calculating the permutations. You can just call the `List permutation(final String str)` method to get the permutations. — marstran, Aug 05 '15 at 19:11
Thanks - Sorry it took so long to add this as best answer, I was just really unsure of how it worked! :) — Slippy, Aug 07 '15 at 13:33

How do I get not just all substrings, but all POSSIBLE substrings of a string?

3 Answers3

Linked