# Longest Common Subsequence | LeetCode | Solution Explained

Longest Common Subsequence. One of the most popular string DP questions. I explain the logic with recursive & iterative dynamic programming approach coded in Python3.

Contents

## Logic

• Let `s` and `t` be source and target sentences
• These are the same as `text1` and `text2`
• Each character is either a part of the answer OR it is not
• Have two pointers i, j pointing to s and t respectively
• if `s[i] == t[j]`,
• we have a match, thus its a good idea to include this character
• if not,
• we try skipping over the character in `s` by doing `i+1` or do skip over character in `t` by doing `j+1`
• we don’t know which is the better case, so we spawn a recursion in both cases and store the max(case1, case2)

## Recursive Solution

```class Solution:
def longestCommonSubsequence(self, s: str, t: str) -> int:

@lru_cache(None)
def recurse(i, j):
if i >= m or j >= n: return 0

if s[i] == t[j]: return 1 + recurse(i+1, j+1)

return max(recurse(i+1, j), recurse(i, j+1))

m, n = len(s), len(t)
return recurse(0, 0)```

## Iterative Solution

We can now just convert the iterative logic into recursive logic.

```class Solution:
def longestCommonSubsequence(self, s: str, t: str) -> int:
m, n = len(s), len(t)
dp = [[0] * (n+1) for _ in range(m+1)]

for i in reversed(range(m)):
for j in reversed(range(n)):
if s[i] == t[j]:
dp[i][j] = 1 + dp[i+1][j+1]
else:
dp[i][j] = max(dp[i+1][j], dp[i][j+1])

return dp[0][0]```
##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Disjoint Intervals | InterviewBit | Solution Explained

June 12, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.