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

Here's a more raw solution.

public int strDist(String str, String sub) {

  //first base case to check if the string doesnt have the substring
  if(str.length() < sub.length()) return 0;

  //check if the string starts with the substring
  if(str.substring(0,sub.length()).equals(sub)){

    //check if the string ends with the substring, if so return the length of the string
    if(str.substring(str.length() - sub.length(),str.length()).equals(sub)){
      return str.length();
    }

    //if the above condition fails, shave the last charater of the string and recurse
    return strDist(str.substring(0,str.length()-1),sub);
  }

  //keep searching for the substring to appear in the string
  return strDist(str.substring(1),sub);
}

Answer 2

A small solution with explanation

public int strDist(String str, String sub) {
  // base case
  if(str.length() < sub.length() || !str.contains(sub)) return 0;

  // success case      
  if(str.startsWith(sub) && str.endsWith(sub)) {
    return str.length(); 
  }

  // cleaning the end of the string to be able to find the success case if exists
  if(str.startsWith(sub)) {
    return strDist(str.substring(0, str.length() - 1), sub);
  }

  // cleaning the begin of the string to be able to find the success case if exists
  return strDist(str.substring(1), sub);
}

Answer 3

this is my way of solving it, it is kinda similar but i find it simpler (hope it helps) :

public int strDist(String str, String sub) { 

  if(str.length() < sub.length())
    return 0;

  if(!str.contains(sub))return 0;

  if(str.startsWith(sub)&& str.endsWith(sub))
    return str.length();

  if(str.startsWith(sub) )
    return  strDist(str.substring(0,str.length()-1),sub);

  if(str.endsWith(sub)) 
    return strDist(str.substring(1,str.length()),sub);

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

Answer 4

Since, others have already answered with the recursive code, I have included an O(n) solution using KMP algorithm

#include <iostream>
#include <vector>
using namespace std;
vector<int> failureFunction(string a){
    int n= a.length();
    vector<int> f(n+1);
    f[0]=f[1]=0;
    for(int i=2;i<=n;i++){
        int j = f[i-1];
        while(1){
            if( a[j]== a[i-1]){
                f[i]= j+1;
                break;
            }
            else if (j==0){
                f[i]= 0;
                break;
            }
            else j = f[j];
        }
    }
    return f;
}
int strDist(string str , string sub ){
    int n= sub.length();
    int m= str.length();
    vector<int> f = failureFunction(sub);
    vector<int> ff(m+1);

    ff[0]= (str[0]==sub[0]) ? 1 : 0;
    for(int i=1;i<m;i++){
        int j = ff[i-1];
        if(j==n)
            j=f[j];
        while(1){
            if(  sub[j] == str[i] ){
                ff[i]= j+1;
                break;
            }
            else if(j==0){
                ff[i]= 0;
                break;
            }
            else j= f[j];
        }
    }
    int first_occ = -1, last_occ= -1;
    for(int i=0;i<m;i++){
        if( ff[i]==n ){
            if( first_occ == -1 ){
                first_occ = i-n+1;
            }
            last_occ = i;
        }
    }
    if ( first_occ == -1 )
        return 0;
    else    
    return last_occ - first_occ + 1;
}   
int main() {
    // your code goes here
    cout<<strDist("catcowcat", "cat")<<endl;
    cout<<strDist("hiHellohihihi", "hih")<<endl;
    cout<<strDist("catcowcat", "cow")<<endl;
    cout<<strDist("cccatcowcatxx", "cat")<<endl;
    cout<<strDist("xx","y");
    return 0;
}

Answer 5

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.

Answer 6

Your implementation is hard to follow. It would be more appropriate to describe the algorithm rather to provide the implementation.

Based on the description, below is my implementation. I think it is concise and easy to understand.

class Example {

    private static int indexOf(String str, int idx, String sub, int res) {

        if (str.length() < sub.length()) return res;

        int tmp = str.indexOf(sub, idx);

        if (tmp < 0) return res;

        return Math.max(tmp, indexOf(str, tmp + 1, sub, res));

    }

    public static int strDist(String str, String sub) {

        if (str.length() < sub.length()) return 0;


        int from = str.indexOf(sub);
        int to = indexOf(str, from + 1, sub, from);


        return to - from + sub.length();
    }

    public static void main(String[] args) {

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

Result:

9
3
9
5