1143. Longest Common Subsequence

Description of Problem

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.

Solution

Tags: Dynamic Programming

Explanation

Look at explanation of LCS from Wikipedia.

Let \(X_i\) and \(Y_i\) are substring of s1 and s2 from index 0 to i (exclusively) (i.e. \(X_i = (x_0,x_1,...x_{i-1})\)) and \(||\) be concatenation opertor.

\[ LCS(X_i, Y_i) = \begin{cases} \epsilon & \text{if i = 0 or j = 0} \\ LCS(X_{i-1}, Y_{i-1}) || x_{i-1} & \text{if i > 0 and j > 0 and } x_{i-1} = y_{i-1} \\ \max(LCS(X_{i}, Y_{i-1}), LCS(X_{i-1},Y_{i})) & \text{if i > 0 and j > 0 and }x_{i-1} \ne y_{i-1} \end{cases}
\]

Since the problem requires us return the length, it requires no back-tracking. We can reduce the space used into 2 rows.

Code (Rust)

impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        let (s1, s2) = (text1.as_bytes(), text2.as_bytes());
        let (m, n) = (s1.len(), s2.len());
        
        let mut dp = vec![ vec![ 0 ; n ] ; 2];
        let mut k = 0;

        for i in 0..m{
            for j in 0..n{
                let n_len = if i >= 1 && j >= 0 { 
                    dp[k^1][j] 
                } else { 
                    0
                };
                
                let w_len = if i >= 0 && j >= 1 { 
                    dp[k][j-1] 
                } else { 
                    0
                };

                let nw_len = if i >= 1 && j >= 1 {
                    dp[k^1][j-1] 
                } else {
                    0
                };

                dp[k][j] = if s1[i] == s2[j] { 
                    1+nw_len
                } else if n_len > w_len { 
                    n_len
                }else {
                    w_len
                };
            }
            k^=1;
        }
        
        return dp[(m-1) % 2][n-1];

    }
}

Complexity

m is length of s1
n is length of s2

Time Complexity

\( T(m,n) = \Theta(m \cdot n) \)

Auxiliary Space

\( S(m,n) = \Theta(m \cdot n) \)
\( S(m,n) = \Theta(n) \) with space optimisation

Leetbook