Longest Common Substring

Given two strings S1 and S2. Find the longest common substring between S1 and S2.
Example: S1 = "LCLC"  S2 = "CLCL"  LCS = "CLC"

Please try solving this problem before jumping on the solution

Click to learn

Subscribe for more updates

Algorithm Visualization

Code Snippet

package com.ideserve.virendra.questions;

import java.util.ArrayList;
import java.util.List;

public class LongestCommonSubstring {
	public static List<String> commonSubstring(String S1, String S2)
		Integer match[][] = new Integer[S1.length()][S2.length()];
		int len1 = S1.length(); 
		int len2 = S2.length();
		int max = Integer.MIN_VALUE; //Maximum length of the string
		ArrayList<String> result = null; //Result list
		for(int i=0; i<len1; i++)
			for(int j=0; j<len2; j++)
				if(S1.charAt(i) ==  S2.charAt(j))
					if ( i == 0 || j==0) 	match[i][j] = 1;
					else    match[i][j] = match[i-1][j-1] + 1;
					if(match[i][j] > max) //If you find a longer common substring re-initialize the max count and update the result list.
						max =  match[i][j];
						result = new ArrayList<String>();
						result.add(S1.substring(i-max+1, i+1)); //substring starts at i-max+1 and ends at i
					else if(match[i][j] == max) // else if you find a common substring with the max length, store it in the list.
						result.add(S1.substring(i-max+1, i+1));
				else  match[i][j] = 0;

		return result;
	public static void main(String args[])
		List<String> result = commonSubstring("CLCL", "LCLC");
		for(String str: result)


Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n^2)


  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa