Returning matching substrings, of n length, at the beginning and end of a string

Question

I am going through the Java CodingBat exercises. Here is the one I have just completed:

Given a string, return the longest substring that appears at both the beginning and end of the string without overlapping. For example, sameEnds("abXab") is "ab".]

Here is my code:

public String sameEnds(String string) {

    int strLength = string.length();

    if (string.substring(0, strLength/2).equals(string.substring(strLength/2, strLength))) {
        return string.substring(0, strLength/2);
    }

    for (int i = 1; i < strLength; i++) {
        if (string.substring(0, i).equals(string.substring(strLength-i, strLength) )) {
            return string.substring(0, i);
        }
    }
    return "";
}

The code passes the majority of the tests without the first if statement, so that was included to ensure it passes circumstances such as an input of xxxx. Without this statement, xxxx returns x, which is incorrect.

My questions are:

1. Is it acceptable/correct to use this 'cautionary' if statement, or should I somehow be incorporating it into the for loop?
2. Would it make sense, for readability and conciseness, to be creating some variables for things like string.substring(), as I did with strLength?
3. Would it make sense to use a StringBuilder? I can't really see how it could be used in this particular case.

4. Does it make sense to use separate return statements, or would it be more useful to assign the outcome to a resultant string, and use only one return statement at the end of the method? i.e.:

   Separate statements of String result = "result here";.

   One statement at the bottom of return result;.

Answer 1

Sometimes a 'guard condition' is needed to ensure that input parameters create a valid condition that can be processed. Other times, you need a condition to handle special cases in special ways.

In your case, however, there is a simple solution which you can affect by changing the limit of your for-loop. Currently, you have:

for (int i = 1; i < strLength; i++) {

If you make that:

for (int i = 1; i <= strLength / 2; i++) {

then the i-loop will never get far enough in to the String to make a problem - remember, the requirement is that the front/back are not overlapping.

For what it's worth, I would consider a loop in the other direction....

for (int i = (strLength / 2) + 1, i < strLength; i++) {
    if (string.startsWith(string.substring(i))) {
        return string.substring(i);
    }
}
return "";

Update: - maaartinus notes this about question 4 (and his answers to your other questions are also great)....

The single-point-of-return paradigm is pretty obsolete for Java. Separate returns are usually much cleaner.

I am a strong believer in early returns in all languages that support them (not all languages do). They are common throughout the Java code-base, and they simplify the variable space tremendously.

I feel it should be taken even further though. I sometimes create functions just to use the early-return feature. Sometimes, when you have nested loops, you want to break from the outer-loop in certain conditions in the inner loop. By putting the inner-loop in a function, you can use a return to 'continue' the loop in a way that is neater than having break and continue logic directly.

The early-return concept is more than just a 'different' way to do things, it can make complicated logic more simple.

Answer 2

Just some answers.

The code passes the majority of the tests without the first if statement, so that was included to ensure it passes circumstances such as an input of xxxx. Without this statement, xxxx returns x, which is incorrect.

You if-statement solves this case... and nothing more. What about xxxxxx? The problem is that you're starting with the shortest match when you should find the longest. Reversing your loop as rolfl wrote is the way to go.

Be careful with such guard conditions. They're OK for special cases, but there's no special case here.

---

2. Would it make sense, for readability and conciseness, to be creating some variables for things like string.substring(), as I did with strLength?

It depends. If an expression gets used a lot, is complicated, or time-consuming than surely use a local variable. In this case, I probably would not.

3. Would it make sense to use a StringBuilder? I can't really see how it could be used in this particular case.

No, you're building nothing.

4. Does it make sense to use separate return statements, or would it be more useful to assign the outcome to a resultant string, and use only one return statement at the end of the method?

The single-point-of-return paradigm is pretty obsolete for Java. Separate returns are usually much cleaner.

Answer 3

Here's a better solution that uses beginsWith() and endsWith() functions: You could even use a StringBuilder for better practice, but I have omitted this because it makes it easier to understand.

public String sameEnds(String string) {
    //Create a return string that is blank.
    String ret = "";
    //Create the maximum amount that we are going 
    //to go both backward and forward in the string
    int maxInt = (string.length() / 2) + 1;
    //We start at iteration 0 for the first check and go up to the maxInt.
    for (int i = 0; i < maxInt; i++)
    {
      //Create a temporary string will change that we will check for the value.
      String temp = string.substring(0, i);
      //If the temporary string is at the beginning and end, we set our return
      //String equal to it.
      if (string.startsWith(temp) && string.endsWith(temp))
      {
        ret = temp;
      }
    }
    //What we end up with is the return string that has the most characters
    //At the beginning and the end.
    return ret;
  }