← Infosys questions
CodingMediumReported in a candidate post, May 2026

Dynamic Programming problem on LCS or Knapsack variant

Filed under Infosys

Free read 3 of 3

Confirm 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

  1. Confirm case sensitivity and whether substring or subsequence is required.

Solution

O(m * n) time, O(m * n) space

Python
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.