Longest Common subsequence.pptx

The Longest Common Subsequence (LCS) programming problem is a fundamental challenge in computer science, finding wide applications in fields such as bioinformatics, text comparison, and version control systems. The essence of LCS lies in identifying the longest possible subsequence common to two given sequences, where a subsequence does not necessarily have to be contiguous. This problem is efficiently solved using dynamic programming, where a table is systematically filled to determine the length of the LCS. The presentation will delve into the basic concepts of LCS, providing a step-by-step explanation of the dynamic programming approach, showcasing visual representations for clarity. Real-world applications, challenges, variants, and code implementations will be discussed, offering a comprehensive understanding of this pivotal problem-solving technique. Additionally, the presentation will touch upon optimizations, enhancements, and potential areas for further exploration. Whether you're a beginner seeking an introduction to LCS or an experienced coder looking for optimization strategies, this presentation aims to provide valuable insights into the Longest Common Subsequence programming problem.

1. Longest common subsequence (LCS)

2. T able of contents 01 03 02 04 Understanding the problem Recursion Memoization Tabulation

3. Understanding The Problem 01

4. Definations A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. e.g. A = bacad (Total possible substring: 2 m ) Substrings: ad, ac, bac, acad, bacad, bcd. A common subsequence of two strings is a subsequence that is common to both strings. A = bacad B = accbadcb common subsequence : ad, ac, bac, acad. The longest common subsequence (LCS) of A and B: acad .

5. Problem Statement Given two strings s1 and s2 , return the length of their longest common subsequence. If there is no common subsequence, return 0. Example: Input: s1 = "abcde", s2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.

6. Let’s try another example INPUT: two strings OUTPUT: longest common subsequence ACTGAACTCTGTGCACT TGACTCAGCACAAAAAC

7. Let’s try another example INPUT: two strings OUTPUT: longest common subsequence AC TGA ACTCTGTGCACT TGA CTCAGCACAAAAAC

8. Let’s try another example INPUT: two strings OUTPUT: longest common subsequence AC TGA A CTC TGTGCACT TGACTC AGCACAAAAAC

9. Let’s try another example INPUT: two strings OUTPUT: longest common subsequence AC TGA A CTC T G TGCACT TGACTC A G CACAAAAAC

10. Let’s try another example INPUT: two strings OUTPUT: longest common subsequence AC TGA A CTC T G TG CAC T TGACTC A GCAC AAAAAC lcs = TGACTCGCAC output = 10

11. Brute Force: For every subsequence of s1 , check whether it’s a subsequence of s2 . s1 has 2 m subsequences. Each subsequence takes Θ(n) time to check: scan s2 for first letter, for second, and so on. Time Complexity : Θ(n2 m ) . m = length of s1 n = length of s2

12. Reccursion 2

13. Alogrithm: Condition 1: Check if both character arrays are empty. If they are empty, return 0. Condition 2: If the character arrays are not empty, then check if the last character of both character arrays matches or not. If you get a match, then return 1 + LCS (Both character arrays with reduced size). Condition 3: If you don’t get a character match, move either one character in the first character array A or the second character array B. Pick whichever produces maximum value.

14. Recursion Tree let’s consider two string A = “XY” , length = 2 B = “XPYQ” , length = 4 XY X P Y Q

15. Memoization (Top down) 3

16. 1. 2. 3.

17. Tabulation (Bottom up) 4

18. Refrences Videos Abdul Bari Articles Leetcode Algotree Simplelearn TakeUForward

19. Thanks!