इंटरएक्टिव पायथन लैब

Longest Common Subsequence

प्लेग्राउंड लोड होने पर ऑटो-रन होता है। अपने पायथन को ट्रेस करने के लिए मेरा कोड चलाएँ पर क्लिक करें — हर कदम लाइव एनिमेटेड।

समझें·लाइन दर लाइन

रीप्ले·कदम दर कदम

चुनौती·निर्देशित संकेत

XP·...

डेटा फ्लो पाइपलाइन

mastery ट्रैक

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

समझें

Line 1

lcs('ABCBDAB', 'BDCAB') called. m=7, n=5.

यह दृष्टिकोण क्यों?

We want the longest subsequence present in both strings. A subsequence doesn't need to be contiguous. BDAB is common with length 4.

Structured Explanation

Overview

Longest Common Subsequence (LCS): do strings ka longest common subsequence ka length return karo.

Analogy

Jaise do schedules compare karke common free slots dhundna.

Step-by-step

dp[i][j]=s1 first i chars aur s2 first j chars ka LCS length
s1[i-1]==s2[j-1] toh dp[i][j]=dp[i-1][j-1]+1
Warna dp[i][j]=max(dp[i-1][j],dp[i][j-1])
dp[m][n] answer hai

Visual

s1="ABCBDAB" s2="BDCAB" dp[m][n]=4 → LCS="BCAB"

Common mistakes

[
"
S
i
r
f
l
e
n
g
t
h
k
e
b
i
n
a
L
C
S
s
t
r
i
n
g
r
e
t
u
r
n
n
a
h
i
k
a
r
s
a
k
t
e
"
,
"
I
n
d
e
x
o
f
f
s
e
t
(
d
p
[
i
]
s
[
i
-
1
]
c
o
r
r
e
s
p
o
n
d
k
a
r
t
a
h
a
i
)
"
]

Practice questions

Sirf length nahi, LCS string bhi reconstruct karo
Longest common substring (contiguous) mein convert karo

Time

O(mn)

Space

O(mn), optimized O(min(m,n))

जटिलता

समय

O(m × n)

स्पेस

O(m × n)

जटिलता अवलोकन

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8range 1-20

N = 8 पर

जटिलता	ऑपरेशन्स
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

चुनौती

'ABCBDAB' और 'BDCAB' का LCS ढूंढें। DP matrix build करें और sequence trace back करें।

संकेत

dp[i][j] = dp[i-1][j-1]+1 if chars match, else max(dp[i-1][j], dp[i][j-1])।

कोड स्टूडियो