dynamic_programming.longest_common_subsequence
==============================================

.. py:module:: dynamic_programming.longest_common_subsequence

.. autoapi-nested-parse::

   LCS Problem Statement: Given two sequences, find the length of longest subsequence
   present in both of them.  A subsequence is a sequence that appears in the same relative
   order, but not necessarily continuous.
   Example:"abc", "abg" are subsequences of "abcdefgh".



Attributes
----------

.. autoapisummary::

   dynamic_programming.longest_common_subsequence.a


Functions
---------

.. autoapisummary::

   dynamic_programming.longest_common_subsequence.longest_common_subsequence


Module Contents
---------------

.. py:function:: longest_common_subsequence(x: str, y: str)

   Finds the longest common subsequence between two strings. Also returns the
   The subsequence found

   Parameters
   ----------

   x: str, one of the strings
   y: str, the other string

   Returns
   -------
   L[m][n]: int, the length of the longest subsequence. Also equal to len(seq)
   Seq: str, the subsequence found

   >>> longest_common_subsequence("programming", "gaming")
   (6, 'gaming')
   >>> longest_common_subsequence("physics", "smartphone")
   (2, 'ph')
   >>> longest_common_subsequence("computer", "food")
   (1, 'o')
   >>> longest_common_subsequence("", "abc")  # One string is empty
   (0, '')
   >>> longest_common_subsequence("abc", "")  # Other string is empty
   (0, '')
   >>> longest_common_subsequence("", "")  # Both strings are empty
   (0, '')
   >>> longest_common_subsequence("abc", "def")  # No common subsequence
   (0, '')
   >>> longest_common_subsequence("abc", "abc")  # Identical strings
   (3, 'abc')
   >>> longest_common_subsequence("a", "a")  # Single character match
   (1, 'a')
   >>> longest_common_subsequence("a", "b")  # Single character no match
   (0, '')
   >>> longest_common_subsequence("abcdef", "ace")  # Interleaved subsequence
   (3, 'ace')
   >>> longest_common_subsequence("ABCD", "ACBD")  # No repeated characters
   (3, 'ABD')


.. py:data:: a
   :value: 'AGGTAB'