Algorithms for Coding Interviews in Java/

...

/

Solution: Longest Common Substring

Solution: Longest Common Substring

This review provides a detailed analysis of the different ways to solve the Longest Common Substring problem.

We'll cover the following...

Solution #1: Brute force

Let’s start by discussing the brute force solution.

Java
class LongestCommonSubstring
{ 
  public static int longestCommonSubstrLengthRec(String s1, String s2, int i1, int i2, int count) {
    if (i1 == s1.length() || i2 == s2.length())
      return count;
    if (s1.charAt(i1) == s2.charAt(i2))
      count = longestCommonSubstrLengthRec(s1, s2, i1 + 1, i2 + 1, count + 1);
    int c1 = longestCommonSubstrLengthRec(s1, s2, i1, i2 + 1, 0);
    int c2 = longestCommonSubstrLengthRec(s1, s2, i1 + 1, i2, 0);
    return Math.max(count, Math.max(c1, c2));
  }
  public static int longestCommonSubstrLength(String s1, String s2) 
  {
    return longestCommonSubstrLengthRec(s1, s2, 0, 0, 0);
  }
  public static void main(String args[]) 
  {
    String s1 = "0abc321";
    String s2 = "123abcdef";
    String s3 = "educative.io/expl";
    String s4 = "educative.io/edpr";
    System.out.println(longestCommonSubstrLength(s1, s2));
    //System.out.println(longestCommonSubstrLength(s3, s4));
  }
};

Explanation

This is a naive solution which finds all the substrings of the two given strings and then discovers the longest common substrings between the two.

  • If the strings have a matching character, we recursively check for the remaining length of each and keep a track of the current matching length (line 8).

  • If the characters don’t match, we start two new recursive calls by skipping those characters from each string (lines 10-11).

  • The length of the longest common substring will be the maximum number returned by the three recursive calls (line 13).

Time complexity

The time complexity of this code is exponential: O(2m+n)O(2^{m+n}).

Notice that the time complexity is so high that the function times out before it can process the longer inputs s3 and s4. Try uncommenting the call on line 28.

The space complexity is O(m+n ...