Determine Prolonged Concordance — Problem Statement & Solution Guide

StringsEasyLongest Common Subsequence

TimeO(m·n)

SpaceO(min(m,n))

Problem Description

You are provided with two sequences of characters, denoted as textA and textB. A subsequence is defined as a sequence that can be derived from an input sequence by deleting zero or more elements without changing the order of the remaining elements. Your task is to compute the length of the longest sequence that is a subsequence of both textA and textB. This sequence does not need to be contiguous within the original strings, but the relative order of characters must be preserved in both instances.

For example, if textA is "abcde" and textB is "ace", the longest common subsequence is "ace", which has a length of 3. If no common characters exist between the two strings, the length of the longest common subsequence is 0.

Implement a function that takes two strings as input and returns an integer representing the length of their longest common subsequence. The solution should efficiently handle the comparison of character positions to determine the maximum matching length.

DSA Pattern Breakdown

"Determine Prolonged Concordance"

easy

WHY DOES IT MATTER?

LCS exemplifies the dynamic programming paradigm of optimal substructure and overlapping subproblems, a cornerstone for many string‑processing, bioinformatics, and version‑control algorithms. Mastering it equips engineers to tackle edit distance, diff tools, and sequence alignment tasks efficiently.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that each cell depends only on its immediate top, left, and top‑left neighbors, allowing us to collapse the 2‑D DP table into two 1‑D arrays, cutting space from O(m·n) to O(min(m,n)) while preserving the O(m·n) time guarantee.

REAL-WORLD CONNECTION

Think of two software branches: the LCS length corresponds to the maximum set of unchanged lines that can be merged without conflict, analogous to finding the longest common history in distributed version control systems.

During an interview, compute the DP table row‑by‑row and store only two rows; also pre‑swap strings so the shorter one drives the inner loop—this minimizes memory and often avoids TLE on tight time limits.

COMPLEXITY AT A GLANCE

⏱ Time:O(m·n)

💾 Space:O(min(m,n))

Core Theory — Why This Approach?

The Longest Common Subsequence (LCS) problem asks for the maximum‑length sequence that appears in the same relative order in two strings, possibly with gaps. A naive solution enumerates all subsequences of one string (2^n possibilities) and checks each against the other, which quickly becomes infeasible for lengths beyond 20. The optimal solution leverages dynamic programming: by defining dp[i][j] as the LCS length of the prefixes textA[0..i‑1] and textB[0..j‑1], we can build the answer bottom‑up using the recurrence dp[i][j] = dp[i‑1][j‑1] + 1 if the characters match, otherwise max(dp[i‑1][j], dp[i][j‑1]). This transforms an exponential‑time combinatorial explosion into a polynomial‑time algorithm that runs in O(m·n) time, where m and n are the input lengths. Space can be reduced to O(min(m,n)) by keeping only two rows (or columns) of the DP table because each state depends only on the previous row/column.

Interview Questions on This Problem

Q1How would you modify the classic LCS DP to also reconstruct the actual subsequence, not just its length?

Maintain a parent pointer or direction matrix while filling dp; after the table is built, backtrack from dp[m][n] following the pointers: move diagonally when characters match (add the character), otherwise move to the larger of the top or left neighbor. This yields one LCS in O(m·n) time and O(m·n) space (or O(min(m,n)) space with additional bookkeeping).

Q2Can you solve LCS in O(m·n) time but O(1) extra space if only the length is required? Explain.

Yes. Since each dp[i][j] depends only on dp[i‑1][j‑1], dp[i‑1][j], and dp[i][j‑1], we can keep two one‑dimensional arrays: previous and current rows. After processing a row, swap them. This uses O(n) space where n = length of the shorter string, effectively O(1) relative to the input size when the shorter string fits in constant memory.

Q3Why does the LCS problem differ from the Longest Common Substring problem, and how does that affect the DP recurrence?

A substring requires contiguous characters, so the DP recurrence includes a reset to zero when characters differ: dp[i][j] = dp[i‑1][j‑1] + 1 if match else 0. For LCS, non‑contiguous matches are allowed, so we take the max of skipping a character from either string. This changes the transition and the final answer (max over the whole table for substring vs dp[m][n] for subsequence).

Examples

Example 1

Input

textA = "abcde", textB = "ace"

Output

Explanation: The characters 'a', 'c', and 'e' appear in the same relative order in both strings. In "abcde", they are at indices 0, 2, and 4. In "ace", they are at indices 0, 1, and 2. No longer subsequence exists, so the length is 3.

Example 2

Input

textA = "xyz", textB = "abc"

Output

Explanation: There are no common characters between "xyz" and "abc". Therefore, the longest common subsequence is empty, resulting in a length of 0.

Example 3

Input

textA = "abcbdab", textB = "bdcaba"

Output

Explanation: One of the longest common subsequences is "bcba" or "bdab". For instance, "bcba" appears in "abcbdab" at indices 1, 2, 4, 6 and in "bdcaba" at indices 0, 2, 4, 5. The length of this subsequence is 4.

Example 4

Input

textA = "a", textB = "a"

Output

Explanation: Both strings consist of the single character 'a'. The character 'a' is a subsequence of both, so the length of the longest common subsequence is 1.

Constraints

1 <= textA.length, textB.length <= 1000
textA and textB consist of lowercase English letters only.

Optimal Approach & Strategy

Use a 2‑D DP table with the recurrence based on character matches, filling it in O(m·n) time, and compress rows to achieve O(min(m,n)) space.

Brute Force Approach

Generate every subsequence of one string (2^n possibilities) and check if it appears as a subsequence in the other, tracking the longest match.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(m·n)

function longestCommonSubsequence(s1, s2) {
   const m = s1.length;
   const n = s2.length;
   const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
   let maxLength = 0;
   for (let i = 1; i <= m; i++) {
       for (let j = 1; j <= n; j++) {
           if (s1[i - 1] === s2[j - 1]) {
               dp[i][j] = dp[i - 1][j - 1] + 1;
               maxLength = Math.max(maxLength, dp[i][j]);
           }
       }
   }
   // Check if the longest common subsequence appears in the same relative order
   let k = maxLength;
   while (k > 0) {
       if (s1.indexOf(s1.slice(s1.length - k, s1.length), 0) === s2.indexOf(s2.slice(s2.length - k, s2.length), 0)) {
           return k;
       }
       k--;
   }
   return 0;
}

class Solution {
public:
   int longestCommonSubsequence(string s1, string s2) {
       int m = s1.length();
       int n = s2.length();
       vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
       int maxLength = 0;
       for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
               if (s1[i - 1] == s2[j - 1]) {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
                   maxLength = max(maxLength, dp[i][j]);
               }
           }
       }
       // Check if the longest common subsequence appears in the same relative order
       int k = maxLength;
       while (k > 0) {
           if (s1.find(s1.substr(s1.length() - k, k)) == s2.find(s2.substr(s2.length() - k, k))) {
               return k;
           }
           k--;
       }
       return 0;
   }
};

class Solution {
   public int longestCommonSubsequence(String s1, String s2) {
       int m = s1.length();
       int n = s2.length();
       int[][] dp = new int[m + 1][n + 1];
       int maxLength = 0;
       for (int i = 1; i <= m; i++) {
           for (int j = 1; j <= n; j++) {
               if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1] + 1;
                   maxLength = Math.max(maxLength, dp[i][j]);
               }
           }
       }
       // Check if the longest common subsequence appears in the same relative order
       int k = maxLength;
       while (k > 0) {
           if (s1.indexOf(s1.substring(s1.length() - k, s1.length()), 0) == s2.indexOf(s2.substring(s2.length() - k, s2.length()), 0)) {
               return k;
           }
           k--;
       }
       return 0;
   }
}

def longest_common_subsequence(s1, s2):
   m, n = len(s1), len(s2)
   dp = [[0] * (n + 1) for _ in range(m + 1)]
   max_length = 0
   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
               max_length = max(max_length, dp[i][j])
   # Check if the longest common subsequence appears in the same relative order
   k = max_length
   while k > 0:
       if s1.index(s1[-k:]) == s2.index(s2[-k:]):
           return k
       k -= 1
   return 0

function longestCommonSubsequence(s1, s2) {
   const m = s1.length;
   const n = s2.length;
   const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
   let maxLength = 0;
   for (let i = 1; i <= m; i++) {
       for (let j = 1; j <= n; j++) {
           if (s1[i - 1] === s2[j - 1]) {
               dp[i][j] = dp[i - 1][j - 1] + 1;
               maxLength = Math.max(maxLength, dp[i][j]);
           }
       }
   }
   // Check if the longest common subsequence appears in the same relative order
   let k = maxLength;
   while (k > 0) {
       if (s1.indexOf(s1.slice(s1.length - k, s1.length), 0) === s2.indexOf(s2.slice(s2.length - k, s2.length), 0)) {
           return k;
       }
       k--;
   }
   return 0;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Determine Prolonged Concordance Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Strings

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Determine Prolonged Concordance — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor