Woodstock Blog

a tech blog for general algorithmic interview questions

[Question] Longest Common Substring



Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

For example, if the given strings are “GeeksforGeeks” and “GeeksQuiz”, the output should be 5 as longest common substring is “Geeks”.


This question is to be distinguished from [LintCode] Longest Common Subsequence.

The solution is DP, too. Even the code is similar. Read my code below.

Updated on Jan 26th, 2015: there is another approach using Suffix Array, suggested by this post - but wait! Do not try to read that article, because you won’t easily understand its explanations. I will summarize it in simple English:

  1. Concatenate String X with a “#” sign, and String Y with a “$” sign.
  2. Build a suffix tree using both strings
  3. find out node with both “$” and “#” as child.

In the case of (X = xabxa, and Y = babxba), the branch “abx” would be the deepest node that qualifies. Thus the result. Code is not written.


public String LCSubstr(String s, String t) {
    int longest = 0;
    int tPos = -1;

    // dp[i][j] represents the LCSubstr ending at position i and j
    int[][] dp = new int[t.length() + 1][s.length() + 1];
    for (int i = 1; i <= t.length(); i++) {
        for (int j = 1; j <= s.length(); j++) {
            if (t.charAt(i - 1) == s.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > longest) {
                    longest = dp[i][j];
                    tPos = i;
    return t.substring(tPos - longest, tPos);