search

AlgoGenesis / C

AlgoGenesis is a centralized open-source platform dedicated to providing optimized and well-documented algorithm implementations in C. Perfect for both beginners and advanced users, this repository serves as a comprehensive learning resource for solving algorithmic challenges.
MIT License
89 stars 306 forks source link

Longest Common Subsequence (LCS) DP #56

Closed yeshwanth-ds closed 1 month ago

yeshwanth-ds commented 1 month ago

The Longest Common Subsequence (LCS) algorithm is a classic dynamic programming problem that identifies the longest subsequence present in both given sequences, where a subsequence is derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

The algorithm typically involves creating a 2D array (or table) to store the lengths of LCS for various pairs of prefixes of the input sequences. By iteratively comparing characters from both sequences and filling in the table based on matches or mismatches, the algorithm efficiently determines the length of the longest common subsequence.

The time complexity of the LCS algorithm is O(m * n), where m and n are the lengths of the two input sequences, making it suitable for moderate-sized strings, while its space complexity can also be optimized to O(min(m, n)).

I would like you to assign me this problem under gssoc-ext

Charul00 commented 1 month ago

can i work on this

pankaj-bind commented 1 month ago

@yeshwanth-ds you can start