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



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