Lesson 4 � Intermediate

LIS, LCS & Edit Distance

Sequences aur strings pe DP lagana sabse powerful technique hai. Longest Increasing Subsequence (LIS) mein array mein se increasing order mein sabse lambi subsequence nikalte hain. Longest Common Subsequence (LCS) mein 2 strings ki longest common part dhundhte hain. Edit Distance mein ek string ko doosre mein convert karne ke minimum steps nikalte hain. Ye teeno problems interview mein bahut aati hain.

? 35 min✓ Intermediate? 0/1 Knapsack

Longest Increasing Subsequence (LIS)

WHAT

Array mein se ek subsequence nikalo jismein elements increasing order mein hon aur length maximum ho. Subsequence mein elements nahi hone chahiye but order maintain hona chahiye. Example: [10, 9, 2, 5, 3, 7, 101, 18] ka LIS = [2, 3, 7, 101] with length 4.

WHEN

Jab "longest increasing/strictly increasing/non-decreasing subsequence" puche, jab sequence mein order maintain karna ho � tab LIS pattern lagao. Patience sorting bhi isi se related hai.

WHERE

LIS, Russian Doll Envelope, Box Stacking, Longest Bitonic Subsequence � sab LIS based hain. O(n log n) solution bhi hai binary search se.

# LIS � O(n^2) DP approach
def lis(arr):
 n = len(arr)
 dp = [1] * n # har element ki minimum length LIS = 1
 
 for i in range(1, n):
 for j in range(i):
 if arr[j] < arr[i]:
 dp[i] = max(dp[i], dp[j] + 1)
 
 return max(dp)

# Example
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"LIS length: {lis(arr)}") # 4

# DP Table:
# arr: 10 9 2 5 3 7 101 18
# dp: 1 1 1 2 2 3 4 4
#
# dp[3] = 2 (2,5) ya (2,3) 
# dp[6] = 4 (2,3,7,101)

LIS Optimization: O(n^2) approach interview mein chalta hai. Agar interviewer puche toh O(n log n) binary search approach bhi aata hona chahiye � patience sorting method.

Longest Common Subsequence (LCS)

Do strings di hain � unki longest common part dhundho. Characters nahi hone chahiye but order maintain hona chahiye:

# LCS � O(m*n) DP approach
def lcs(s1, s2):
 m, n = len(s1), len(s2)
 dp = [[0] * (n + 1) for _ in range(m + 1)]
 
 for i in range(1, m + 1):
 for j in range(1, n + 1):
 if s1[i - 1] == s2[j - 1]:
 dp[i][j] = dp[i - 1][j - 1] + 1 # Match! diagonal + 1
 else:
 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # Max of upar/baayan
 
 return dp[m][n]

# Example
s1 = "abcde"
s2 = "ace"
print(f"LCS length: {lcs(s1, s2)}") # 3 (ace)

# DP Table:
# "" a c e
# "" 0 0 0 0
# a 0 1 1 1
# b 0 1 1 1
# c 0 1 2 2
# d 0 1 2 2
# e 0 1 2 3

LCS Table Fill Trace

# LCS Decision Logic:
#
# Agar s1[i] == s2[j]:
# ✓ Match mila! dp[i][j] = dp[i-1][j-1] + 1
# ✓ Diagonal se + 1
#
# Agar match nahi:
# ✓ Ya toh s1 ka character skip karo (dp[i-1][j])
# ✓ Ya toh s2 ka character skip karo (dp[i][j-1])
# ✓ Max lo dono mein se
#
# LCS actual string nikalna hai toh:
# Table ke last cell se backtrack karo
# Diagonal jaao jab match ho
# Upar/baayan jaao jab match na ho

Edit Distance (Levenshtein Distance)

Ek string ko doosre mein convert karo minimum operations se. Operations: insert, delete, replace. Kitne minimum steps chahiye?

# Edit Distance � O(m*n) DP approach
def editDistance(s1, s2):
 m, n = len(s1), len(s2)
 dp = [[0] * (n + 1) for _ in range(m + 1)]
 
 # Base cases: empty string se conversion
 for i in range(m + 1):
 dp[i][0] = i # i deletes to make empty
 for j in range(n + 1):
 dp[0][j] = j # j inserts to make s2
 
 for i in range(1, m + 1):
 for j in range(1, n + 1):
 if s1[i - 1] == s2[j - 1]:
 dp[i][j] = dp[i - 1][j - 1] # Match � kuch mat karo
 else:
 dp[i][j] = 1 + min(
 dp[i - 1][j], # Delete
 dp[i][j - 1], # Insert
 dp[i - 1][j - 1] # Replace
 )
 
 return dp[m][n]

# Example
s1 = "horse"
s2 = "ros"
print(f"Edit Distance: {editDistance(s1, s2)}") # 3

# Operations: horse ✓ rorse (replace h?r)
# rorse ✓ rose (delete r)
# rose ✓ ros (delete e)
# Total: 3 operations

Edit Distance = LCS relation: Edit Distance = m + n - 2*LCS. Agar LCS pata hai toh edit distance turant nikal sakte ho. But DP se seedha bhi kar sakte ho � dono approaches valid hain.

Try it: code khud likho

Exercise

Question: Strings s1 = "abc" aur s2 = "def" ki LCS length kya hogi✓ Sirf number daalo.

Question: Edit Distance mein kitne operations available hain✓ Number daalo.

Common mistakes

LIS mein subsequence vs subarray confuse karna: Subsequence nahi honi chahiye but subarray continuous hoti hai. LIS subsequence hai � elements skip kar sakte ho.
LCS mein diagonal vs max confuse karna: Jab characters match hon toh dp[i-1][j-1] + 1 (diagonal). Jab match na hon toh max(dp[i-1][j], dp[i][j-1]) (upar ya baayan). Dono alag hain.
Edit Distance base case miss karna: dp[i][0] = i (i deletes) aur dp[0][j] = j (j inserts). Bina base case ke table galat fill hogi.
1-indexing confusion: DP array 1-indexed hai but strings 0-indexed. Isliye s1[i-1] access karte hain jab dp[i] use karte ho.
Space optimization skip karna: LCS mein sirf current row aur previous row chahiye � 2D ki jagah 1D array use karo. Time same rahega but space O(n) ho jaayega.

Lesson complete?

LIS, LCS aur Edit Distance samajh aa gaya✓ Ab strings aur grids pe DP dekhte hain � Palindrome, Word Break, Unique Paths jaise problems.