Codingbat challenge: sameEnds

user_16561343 0
Viewed 118

Given task sameEnds from CodingBat:

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".

sameEnds("abXYab") → "ab"
sameEnds("xx") → "x"
sameEnds("xxx") → "x"

My solution passes all the tests except one^:

public String sameEnds(String string) {
  String substringFront = "";
  String substringEnd = "";
  String longestSubstring = "";
  
  for (int i = 1; i < string.length() - 1; i++) {
    substringFront = string.substring(0, i);
    substringEnd = string.substring(i);
    
    if (substringEnd.contains(substringFront)) {
      longestSubstring = substringFront;
    }
  }
  
  return longestSubstring;
}

What is the problem here? How could I fix it?

enter image description here

matching substring java string
3 Answers

In addition to the technical issues that @Dan and others have aptly pointed out, I want to highlight the issue of unnecessary complexity, which in many cases leads to such logical errors.

Given this, and considering that this is a challenge, I would prefer a minimalist approach, like the one below, which is self-explanatory and hence simple to comprehend and debug.

public String sameEnds(String string) {
  int middle = string.length() / 2;
  for (int i = middle; i >= 0; i--) {
    String left = string.substring(0, i);
    if (string.endsWith(left)) {
      return left;
    }
  }
  return "";
}
user_191705340

There are a couple of problems within your code:

  • You stop iterating before reaching the last character, instead of iterating till length/2 included (you need to check the beginning and end without overlapping so no need to iterate till the end or almost).

  • You substringEnd should start from the right side, so it should look like string.substring(string.length() - i);.

Here is a fixed implementation:

public static void main(String[] args) {
    List<String> listTest = List.of("abXYab", "xx", "xxx", "xxxx", "javaXYZjava", "javajava", "Hello! and Hello!", "x", "", "abcd", "mymmy");
    String substringFront, substringEnd, longestMatch;
    for (String string : listTest) {
        longestMatch = "";
        for (int i = 1; i <= string.length() / 2; i++) {
            substringFront = string.substring(0, i);
            substringEnd = string.substring(string.length() - i);

            if (substringEnd.equals(substringFront) && substringEnd.length() > longestMatch.length()) {
                longestMatch = substringEnd;
            }
        }

        if (!listTest.equals("")) {
            System.out.printf("%s => %s%n", string, longestMatch);
        } else {
            System.out.printf("%s => null%n", string);
        }
    }
}

Here is a link to test the code above:

https://www.jdoodle.com/iembed/v0/rEO

However, to make it more concise you could use a regex which uses a capturing group with a greedy quantifier to match at the beginning of the string and make sure that what has been captured at the beginning matches also at the end.

^(.+)(.*)\1$

Here is a link to test the regex:

https://regex101.com/r/cgowDQ/1

This could be written in Java like so:

public static void main(String[] args) {
    List<String> listTest = List.of("abXYab", "xx", "xxx", "xxxx", "javaXYZjava", "javajava", "Hello! and Hello!", "x", "", "abcd", "mymmy");
    Pattern pattern = Pattern.compile("^(.+)(.*)\\1$");
    Matcher matcher;
    for (String s : listTest) {
        matcher = pattern.matcher(s);
        if (matcher.find()) {
            System.out.printf("%s => %s%n", s, matcher.group(1));
        } else {
            System.out.printf("%s => null%n", s);
        }
    }
}

Here you can test the code above:

https://www.jdoodle.com/iembed/v0/rEK

user_44156250

Iterate till the last element in the String, changing the loop condition fixes the problem.

for (int i = 1; i < string.length(); i++)
user_136799030
Related