Compute the length of largest substring that starts and ends with the same substring

Question

Below is the Problem Statement:

PS: 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

Below is my Code: (Without recursion)//since i found it hard to implement with recursion.

    public int strDist(String str, String sub){    
        int idx = 0;     
        int max;    
        if (str.isEmpty()) max = 0;    
        else max=1;                        
        while ((idx = str.indexOf(sub, idx)) != -1){     
            int previous=str.indexOf(sub, idx);     
            max = Math.max(max,previous);     
            idx++;                           
        }     
     return max;    
   }

Its working for few as shown below but returns FAIL for others.

Expected This Run
strDist("catcowcat", "cat") → 9 6 FAIL
strDist("catcowcat", "cow") → 3 3 OK
strDist("cccatcowcatxx", "cat") → 9 8 FAIL
strDist("abccatcowcatcatxyz", "cat") → 12 12 OK
strDist("xyx", "x") → 3 2 FAIL
strDist("xyx", "y") → 1 1 OK
strDist("xyx", "z") → 0 1 FAIL
strDist("z", "z") → 1 1 OK
strDist("x", "z") → 0 1 FAIL
strDist("", "z") → 0 0 OK
strDist("hiHellohihihi", "hi") → 13 11 FAIL
strDist("hiHellohihihi", "hih") → 5 9 FAIL
strDist("hiHellohihihi", "o") → 1 6 FAIL
strDist("hiHellohihihi", "ll") → 2 4 FAIL

Could you let me whats wrong with the code and how to return the largest substring that begins and ends with sub with its respective length.

Answer 1

There's a simple solution that's much more efficient. Find the first and last occurrence of the substring and you have your answer. No need to search for all occurrences.

public int strDist(String str, String sub) {
  int first = str.indexOf(sub);
  if (first == -1)
    return 0;
  int last = str.lastIndexOf(sub);
  return last - first + sub.length();
}

http://ideone.com/3mgbK

The problem with your code is that you are returning the index of the last occurrence of the substring. You appear to be trying to find the 2nd last occurrence as well, and your last line should be max - previous at the least, but then you'd also need to add the length of the substring making it max - previous + sub.length(). You also need to move the declaration of previous outside the while loop. But then you're finding the distance between the 2nd last and last occurrences, which will fail if there aren't exactly 2 occurrences (e.g. "foocatbar" or "catfoocatbarcat").

Solving this recursively is a bit overkill, first and foremost because you cannot use the builtin String.indexOf() function. But since this is homework, here's a quick attempt:

public static int indexOf(String str, String sub, int start, int direction) {
  if (start < 0 || start > str.length() - sub.length())
    return -1;
  if (str.substring(start, start + sub.length()).equals(sub))
    return start;
  return indexOf(str, sub, start+direction, direction);
}

public static int strDistRecursive(String str, String sub) {
  int first = indexOf(str, sub, 0, 1);
  if (first == -1)
    return 0;
  int last = indexOf(str, sub, str.length() - sub.length(), -1);
  return last - first + sub.length();
}

http://ideone.com/f6bok