Non-Contiguous Substrings

Problem:


A non-contiguous substring of string \$s\$ is a sequence of \$k \geq 0\$ characters in \$s\$, in the order in which they occur in \$s\$. For instance, the set of all non-contiguous substring of "abcd" are \$\{a,cd\}, \{ab,d\}, \{a,c\}, \{a,d\}, \{b,d\}\$.

I want to mention this is from an assignment (which I completed and submitted more than a week before asking this) and the reason I'm asking is because I'm curious if there is a better, more elegant method than mine.

This is supposed to be done recursively.

My solution:

Find all possible substring (powerset) of the given string (recursive function). Test each possible substring to see if it is non-contiguous (iterative function).

```
import java.util.Arrays;

public class HWK3_2_hoodav {

public static void main(String[] args) {
/** Parses input and calls powerSet method with input */
String input = Arrays.toString(args);
input = input.substring(1, input.length()-1);
powerSet(input, "", input);
}

public static void powerSet(String original, String base, String substring) {
/** This method recursively finds all possibile combinations of
substrings and then invokes the nonContiguous method to check
if a specific combination is non-contiguous */

if (substring.length() == 1) {
nonContiguous(original, base + substring);
nonContiguous(original, base + " ");
}
else {
powerSet(original, base + substring.charAt(0), substring.substring(1));
powerSet(original, base + " ", substring.substring(1));
}
}

public static void nonContiguous(String original, String candidate) {
/** This method verifies a given candidate is non-contiguous */
if (candidate.contains(" ")) {
for (int i=0; i < original.length(); i++) {
if (candidate.charAt(i) != ' ') {
for (int j=i+1; j < original.length(); j++) {

Bugs in nonContiguous

If your input string contains spaces then your nonContiguous function produces arbitrary output regardless of whether you are correct or not.

-
False positive: As mentioned in the comments, input string "X Z" will print as a non-contiguous subset of itself.

-
False negative: What if the input string is " " (three spaces)? When you build a substring of the first space with the third space this should still count as a non-contiguous subset.

Other problems

-
Base case: If input="" then your base case of recursion (substring.length() == 1) does not work.

-
Naming: substring is not a good name for the parameter in your function. While the name does indicate what the value represents, its name may confuse someone into thinking that it holds the non-contiguous substring when really it just holds the unvisited portion of the original string. For a lack of a better name, I will simply call this value str.

Another approach

This is a fairly poor analogy but here it goes anyway. What if I told you to flip through a deck of cards and tell me if there are any Jokers? Which approach do you think is better?

-
A) When you see a Joker you insert a Queen into the deck after the Joker and look for that Queen afterwards (not knowing if there were any Queens in the original deck or not).

-
B) When you see a Joker you write down that you saw a Joker on a scratch sheet of paper.

I hope we can agree that B is the simpler approach. In this case the Jokers are simply gaps between characters chosen from the input string.

The problem with integrating this logic with your approach is the order in which the recursion is performed. You know when you skip a character (currently when you are adding a " ") but you need to know that another character is added after the skip for you to declare the string as non-contiguous. The method is shown below:

public static void main(String[] args) throws java.lang.Exception
{
    /** Parses input and calls powerSet method with input */
    String input = "abcde";
    nonContiguousSubstrings("", input, true, false);
}

public static void nonContiguousSubstrings(String base, String str, boolean contiguous, boolean skipped)
{
    // This stop condition is simpler and safer.
    // If the original input is empty it stops the recursion here     
    if (str.length() == 0)
    {
        // only print the string if it is not contiguous
        if(!contiguous)
        {
            System.out.println(base);
        }
    }
    else
    {
        // This is the recursion where we skip a character here
        // Set skipped only if we already had a character in base
        // Even if we already had a character in base, we cannot say this skip makes the string non-contiguous unless we add a character to it later
        nonContiguousSubstrings(base, str.substring(1), contiguous, base.length() != 0);

        // Below is the recursion where we add a character here
        // Since we are adding a character to the string, set contiguous to false if we skipped a character previously, otherwise retain its value.
        contiguous = contiguous && !skipped;
        nonContiguousSubstrings(base + str.charAt(0), str.substring(1), contiguous, skipped);
    }
}

Yet Another Approach

By restructuring the recursion we can remove the skipped parameter. The trick is to use recursion only when needed. Iteration suffices to skip indices but we "must" recurse to choose an arbitrary number of elements from input.

Here is a simple substring printer (powerset) using this method:

public static void main(String[] args) throws java.lang.Exception
{
    String input = "abcde";

    // Initially the substring is empty
    allSubstrings(input, "");
}

public static void allSubstrings(String str, String substring)
{
    for (int i = 0; i < str.length(); i++) 
    {
        // For each i, we skip i characters when generating the substring
        allSubstrings(str.substring(i + 1), substring + str.charAt(i));
    }

    System.out.println(substring);
}

Now you just want to be able to detect if there is a gap in each substring. This can be done quite simply if you keep track of whether you ever add a gap. Use a boolean instead of manipulating the string.

```
public static void main(String[] args) throws java.lang.Exception
{
String input = "abcde";

// Initially the substring is empty and deemed contiguous
nonContiguousSubstrings(input, "", true);
}

public static void nonContiguousSubstrings(String str, String substring, boolean contiguous)
{
for (int i = 0; i < str.length(); i++)
{
// There is a gap here iff i doesn't equal 0 (we skip characters) AND we are not creating the first character of the substring.
boolean gapHere = (i != 0) && (substring.length() != 0);

// The substring is still contiguous iff it was already contiguous and there is no gap here
nonContiguousSubstrings(str.substri

StackExchange Code Review Q#108313, answer score: 2