Longest Common Subsequence

Given two strings S1 and S2. Find the longest common subsequence between S1 and S2.
Example: Input- S1 = "ACBEA" S2 = "ADCA"  Output- "ACA"


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.virendra.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Longest common subsequence - Dynamic Programming Solution</b><br>
 * Given two strings S1 and S2. Find the longest common subsequence between S1 and S2.
 * <br><br>
 * Example: <br>
 * Input String: <br>
 *  S1 = "ACBEA"
 *	S2 = "ADCA"
 * <br>
 * Output: <br>
 * ACA
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=7KcR7fN4-CA">Longest Common Subsequence Solution Youtube Link</a> 
 * @author Virendra
 *
 *
 */

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



public class LongestCommonSubsequence {
	public static void commonSubsequence(String S1, String S2)
	{
		int s1_len = S1.length(); 
		int s2_len = S2.length();
	    final int pick_s1_or_s2 = 0;
		final int pick_s1 = 1;
		final int pick_s2 = 2;
		int match[][] = new int[s1_len][s2_len];
		int pointer[][]  = new int[s1_len][s2_len];
		
		
		for(int i=0; i<s1_len; i++)
		{
			for(int j=0; j<s2_len; j++)
			{
				if(S1.charAt(i) ==  S2.charAt(j)) //Characters match
				{    
					if((i==0) || (j==0)) //first row or first column
					{
						match[i][j] = 1; //initialize
					}
					else
					{
						match[i][j] = match[i-1][j-1] + 1;
					}
					pointer[i][j] = pick_s1_or_s2;  
				}
				else  //Characters mismatch
				{	
					if((i > 0 ) && (j > 0)) //neither the first row nor first column
					{
						//Refer in ppt :- LCS(ACBE,ADC) = max(LCS(ACB,ADC), LCS(ACBE,AD))
						//Thumb rule:- mismatch take max. if not in first row or column.
						if(match[i-1][j] >= match[i][j-1])
						{
							match[i][j] = match[i-1][j];
							pointer[i][j] = pick_s2; //ditch s1's character
						}
						else
						{
							match[i][j] = match[i][j-1];
							pointer[i][j] = pick_s1;//ditch s2's character.
						}
					} 
					else if ((i==0) && ( j > 0)) //first row
					{
						match[i][j] = match[i][j-1];
						pointer[i][j] = pick_s1;
					}
					else if((j==0) && (i>0)) //first column
						
					{
						match[i][j] = match[i-1][j];
						pointer[i][j] = pick_s2;
					}
					
				}
				
			}
		}
		
	
		//Printing the LCS.
		int i = s1_len - 1;
		int j = s2_len - 1;
		StringBuffer result = new StringBuffer();
		
		while(i>=0 && j>=0)
		{
			switch(pointer[i][j])
			{
			   //go diagonal and collect the matched character
				case pick_s1_or_s2: 
					result.append(S1.charAt(i));
					i--;
					j--;
					break;
				case pick_s1://go left
					j--;
					break;
				case pick_s2://go up
					i--;
					break;
			}
		}
		
		System.out.println(result.reverse());
		
	}
	
	public static void main(String args[])
	{
		commonSubsequence("ACBEA", "ADCA");
	}

}
		

Order of the Algorithm

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


Contribution

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

    Virendra Karappa

    Ninja Programmer