Dynamic Programming problem on LCS or Knapsack variant
Filed under Infosys
Free read 3 of 3Confirm case sensitivity and whether substring or subsequence is required.
The question
Solve a classic Dynamic Programming problem such as finding the length of the Longest Common Subsequence (LCS) between two given strings.
Constraints
- 1 <= text1.length, text2.length <= 1000
- Strings consist of lowercase English characters
Examples
- Input
- text1 = "abcde", text2 = "ace"
- Output
- 3
- Why
- The longest common subsequence is "ace" with length 3.
Approach
Confirm case sensitivity and whether substring or subsequence is required.
Generate all subsequences of both strings and find the longest match, exponential time.
Use 2D DP table where dp[i][j] represents LCS of text1[0..i-1] and text2[0..j-1]. Fill table iteratively in O(m * n) time.
One or both strings being empty.
Solution
O(m * n) time, O(m * n) space
def longest_common_subsequence(text1, text2):
dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
for i in range(1, len(text1) + 1):
for j in range(1, len(text2) + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
Tips
- What they are testing: Test with completely identical strings, completely disjoint strings, and empty string inputs.
- Common mistake: Off-by-one errors in 2D DP table dimensions or failing to initialize base cases correctly.
Related Infosys questions
Collected from public candidate posts and coding forums. Updated Nov 2026.