9. Longest repeating subsequence(similar to LCS)

-

9. Longest repeating subsequence(similar to LCS)


Problem link :- click here


package programs;

public class String__9
{

	/*
	 	Longest repeating subsequence
	 		1)   s = "AABEBCDD" 		2)   str = "AXXXY"
	 		output = "ABD"		          output = "XX"
	 		
	 	To understand this problem we need to know Longest common subsequence(LCS)
	 			s1 = "ABCDGH"    and   s2 = "AEDFHB"
	 				     output = "ADH"
	 				     
	 	in this problem we have to find the longest no. of common elements from both the
	 	strings that are in SAME ORDER
	 	
	 	APPROACH ------>   DYNAMIC PROGRAMMING
	 	
	 	we will take a matrix of length      s1.length()+1       &         s2.length()+1
	 	our OUTPUT will be the last element of the matrix      
	 	one row extra because we are initiating the value of a block(i-row j-column)
	 		based on the previous row(i-1) and previous column(j-1)
	 	and yes our first row and first column will be zero
	 	
	 	so our actual count of index will be from 1 in matrix 
	 	but in string it will be as usual  from 0
	 	so if we finding the value of         mat[i][j]
	 	we have to consider the characters at index        i-1        &       j-1
	 	
	 	while iterating
	 	we compare the values of           s1[i-1]       &         s2[j-1]
	 	if  they are same           we will take the diagonal element and add 1 and store
	 			mat[i][j] = mat[i-1][j-1] + 1
	 	if they are not same       we will store maximum of the left cell and top cell
	 			mat[i][j] = Math.max( mat[i][j-1] ,  mat[i-1][j]  )
	 	
	 	
	 	In our main problem we have to use a character only once for a subsequence
	 	so lets add a condition in if statement       i != j
	 */
	
	static int longestRepeatingSubsequence(String s)
	{
		//lets store the string to a character array
		char str[] = s.toCharArray();
		int n= str.length;
		
		int mat[][] = new int[n+1][n+1];
		
		//first row zero
		for(int i=0; i<n+1; i++)
			mat[0][i] = 0;
		
		//first column zero
		for(int i=0; i<n+1; i++)
			mat[i][0] = 0;
		
		for(int i=1; i<n+1; i++)
		{
			for(int j=1; j<n+1; j++)
			{
				if(str[i-1] == str[j-1]     &&     i != j )
					mat[i][j] = mat[i-1][j-1] + 1;
				else
					mat[i][j] = Math.max( mat[i][j-1], mat[i-1][j] );
			}
		}
		
		return mat[n][n];
	}
	
	public static void main(String[] args)
	{
		String s = "AABEBCDD";
		
		int ans = longestRepeatingSubsequence(s);
		System.out.println("longest subsequence : " + ans);
	}

}

Time complexity :- O(n^2)
Space complexity :- O(n^2)

Comments

Post a Comment

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

-
Image
4.Sort an array of 0's, 1's & 2's. Problem link :- click here C code #include<stdio.h> void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void sort_012(int A[], int n) { int i, j, m; i = 0; j = n-1; m = 0; while(m<=j) { if(A[m] == 0) { swap(&A[i], &A[m]); i++; m++; } else if(A[m] == 1) { m++; } else { swap(&A[j], &A[m]); j--; } } } void main() { int arr[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array(only 0, 1, or 2)\n"); for(i=0; i<n; i++) scanf("%d",&arr[i]); printf("Given Array\n"); for(i=0; i<n; i++) printf("\t%d",arr[i]); printf("\n...
Read more

1. Reverse

-
Image
1. Reverse the Array.   Problem link :- Reverse the array Algorithm idea :- C code //Reverse the array #include<stdio.h> void rev_arr(int arr[], int start, int end) { int temp; while(start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } void print_arr(int arr[], int size) { int i; for(i=0; i<size; i++) printf("\t%d",arr[i]); printf("\n"); } void main() { int arr1[30]; int n, i; printf("Enter the size of the array\n"); scanf("%d",&n); printf("Enter the elements of the array\n"); for(i=0; i<n; i++) scanf("%d",&arr1[i]); printf("Array before reversing\n"); print_arr(arr1, n); rev_arr(arr1, 0, n-1); printf("\nArray after reversing\n"); print_arr(arr1, n); } Java code //Reverse the array package programs;...
Read more

3. Height of Binary tree

-
3. Height of Binary tree Problem link :- click here package Binary_Tree; public class BinaryTree__3 { static int heightOfTree(Node root) { if(root == null) return 0; int left_height = heightOfTree(root.left); int right_height = heightOfTree(root.right); return Math.max(left_height, right_height) + 1; } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); int arr[] = {2, -1, 3, -1, -1, 3}; tree.root = tree.createTree(arr, 0); int ans = heightOfTree(tree.root); System.out.println("Height : " + ans); } } Time complexity :- O(n) Space complexity :- O(n)
Read more