Longest Common Subsequence

Given two strings, 'S' and 'T' with lengths 'M' and 'N', find the length of the 'Longest Common Subsequence'.

For a string 'str'(per se) of length K, the subsequences are the strings containing characters in the same relative order as they are present in 'str,' but not necessarily contiguous. Subsequences contain all the strings of length varying from 0 to K.

Example :
Subsequences of string "abc" are:  ""(empty string), a, b, c, ab, bc, ac, abc.
Input format :
The first line of input contains the string 'S' of length 'M'.

The second line of the input contains the string 'T' of length 'N'.
Output format :
Return the length of the Longest Common Subsequence.
Constraints :
0 <= M <= 10 ^ 3
0 <= N <= 10 ^ 3

Time Limit: 1 sec
CodingNinjas
author
2y
Memoization

Let the two strings be x and y.

Let x(i) be the substring of x from index 0 to index i.

Let c[i, j] be the length of the longest common subsequence of strings x(i) and y(j).

Then the recurre...read more

CodingNinjas
author
2y
Iterative DP

Let the two strings be x and y.

Let x(i) be the substring of x from index 0 to index i.

Let c[i, j] be the length of the longest common subsequence of strings x(i) and y(j).

Then the recurr...read more

CodingNinjas
author
2y
2 Rows Approach

In each iteration of the outer loop in iterative ‘DP’ we only, need values from all columns of the previous row so instead of making an ('M' + 1) * ('N' + 1) sized array (referred to as...read more

Add answer anonymously...
Amazon Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions
Get AmbitionBox app

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter