:orphan:

Longest Common Subsequence
==========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/longest-common-subsequence/

Given two strings ``text1`` and ``text2``, return *the length of their
longest* **common subsequence**\ *.* If there is no **common
subsequence**, return ``0``.

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.

- For example, ``"ace"`` is a subsequence of ``"abcde"``.

A **common subsequence** of two strings is a subsequence that is common
to both strings.

 

**Example 1:**

::


   Input: text1 = "abcde", text2 = "ace" 
   Output: 3  
   Explanation: The longest common subsequence is "ace" and its length is 3.

**Example 2:**

::


   Input: text1 = "abc", text2 = "abc"
   Output: 3
   Explanation: The longest common subsequence is "abc" and its length is 3.

**Example 3:**

::


   Input: text1 = "abc", text2 = "def"
   Output: 0
   Explanation: There is no such common subsequence, so the result is 0.

 

**Constraints:**

- ``1 <= text1.length, text2.length <= 1000``
- ``text1`` and ``text2`` consist of only lowercase English characters.

.. highlight:: python

Pattern
-------
String, Dynamic Programming

Approaches
----------

.. tab-set::

    .. tab-item:: Dynamic Programming

        **Code**

        .. literalinclude:: ../problems/medium/longest-common-subsequence/longest_common_subsequence__dynamic_programming.py
            :language: python
            :lines: 12-

        **Test**

        >>> from longest_common_subsequence__dynamic_programming import longestCommonSubsequence
        >>> longestCommonSubsequence("abcde", "ace")
        3
        >>> longestCommonSubsequence("abc", "abc")
        3
        >>> longestCommonSubsequence("abc", "def")
        0

        .. autofunction:: longest_common_subsequence__dynamic_programming.longestCommonSubsequence