Compute recursively the largest substring which starts and ends with sub and return its length

Question

The task is: Given a string and a non-empty substring sub, compute recursively the largest substring which starts and ends with sub and return its length.

Examples:

strDist("catcowcat", "cat") → 9
strDist("catcowcat", "cow") → 3
strDist("cccatcowcatxx", "cat") → 9

Can you please look at my code and tell me what is the problem with it?

public int strDist(String str, String sub) {
    if (str.length() < sub.length())
        return 0;

    if (str.length() == sub.length() && str.equals(sub))
        return str.length();

    if (str.length() < 2) {
        if (str.contains(sub)) {
            return 1;
        }
        return 0;
    }

    if (str.length() == 2) {
        if (sub.length() == 2 && str.equals(sub))
            return 2;

        if (str.contains(sub))
            return 1;

        return 0;
    }

    if (str.length() > 2) {
        if (str.startsWith(sub) && str.endsWith(sub)) {
            return str.length();
        }

        if (str.substring(0, sub.length()).equals(sub)) {
            strDist(str.substring(0, str.length() - 2), sub);
        }

        if (str.substring(str.length() - sub.length(), str.length() - 1).equals(sub))
            strDist(str.substring(1, str.length() - 1), sub);
    }
    return strDist(str.substring(1, str.length() - 1), sub);
}

it doesn't work for the case strDist("hiHellohihihi", "hih") → 5 and returns zero.

Answer 1

First, to answer your question, I found a number of issues in your code. My corrected version follows, with comments about the changes I did.

public int strDist(String str, String sub) {

    if (str.length() < sub.length())
        return 0;
    // simplified condition
    if (str.equals(sub))
        return str.length();

    if (str.length() < 2) {
        if (str.contains(sub)) {
            // corrected (if str and sub are both empty strings, you don’t want to return 1)
            return str.length();
        }
        return 0;
    }

    // deleted str.length() == 2 case that didn’t work correctly

    if (str.startsWith(sub) && str.endsWith(sub)) {
        return str.length();
    }
    if (str.startsWith(sub)) { // simplified
        // subtracting only 1 and added return statement
        return strDist(str.substring(0, str.length() - 1), sub);
    }
    // changed completely -- didn’t understand; added return statement, I believe this solved your test case
    if (str.endsWith(sub))
        return strDist(str.substring(1), sub);
    return strDist(str.substring(1, str.length() - 1), sub);

}

Now if I do:

    System.out.println(strDist("catcowcat", "cat"));
    System.out.println(strDist("catcowcat", "cow"));
    System.out.println(strDist("cccatcowcatxx", "cat"));
    System.out.println(strDist("hiHellohihihi", "hih"));

I get:

9
3
9
5

Second, as I said in a comment, I see no point in using recursion here (except perhaps for the exercise). The following version of your method doesn’t, it’s much simpler and it works the same:

public int strDist(String str, String sub) {
    int firstOccurrence = str.indexOf(sub);
    if (firstOccurrence == -1) { // sub not in str
        return 0;
    }
    int lastOccurrence = str.lastIndexOf(sub);
    return lastOccurrence - firstOccurrence + sub.length();
}

Finally, and this may or may not be helpful, a recursive version needs not be as complicated as yours:

public int strDist(String str, String sub) {
    if (sub.isEmpty()) {
        throw new IllegalArgumentException("sub mustn’t be empty");
    }
    if (str.length() <= sub.length()) {
        if (str.equals(sub)) {
            return str.length();
        } else { // sub cannot be in str
            return 0;
        }
    }
    if (str.startsWith(sub)) {
        if (str.endsWith(sub)) {
            return str.length();
        } else {
            return strDist(str.substring(0, str.length() - 1), sub);
        }
    } else {
        return strDist(str.substring(1), sub);
    }
}

It’s fine to get something to work first if you can, even if it’s not the most simple and elegant solution. When either it works or it doesn’t, is a good time to think of ways to simplify. It will make it easier to nail down the bug(s) and also ease maintenance later. Special cases, like length 1 and length 2, are often a good candidate for simplification: see if the general code already caters for them or can easily be made to.