Ways to Increase LCS by One

Problem Overview

Recomputing LCS for every insertion is too slow.

Intuition

Recomputing LCS for every insertion is too slow. Instead, precompute prefix LCS (lcsl) and suffix LCS (lcsr). When you insert character c at position i in s1 and match it with s2[p], the new LCS is lcsl[i][p−1] + 1 + lcsr[i+1][p+1]. That equals base + 1 exactly when lcsl[i][p−1] + lcsr[i+1][p+1] == base — the prefix and suffix already account for the full original LCS, and c adds one more match.

Algorithm

1Build lcsl[i][j] = LCS of s1[0..i−1] and s2[0..j−1] (1-indexed DP).
2Build lcsr[i][j] = LCS of s1[i−1..] and s2[j−1..] by filling the table backwards.
3Store 1-based positions of each letter in s2 for fast lookup.
4For each insertion index i (0..n1) and each letter c, scan positions p in s2 where s2[p−1] == c.
5If lcsl[i][p−1] + lcsr[i+1][p+1] == baseLCS, count this insertion once (break after first valid p).

Example Walkthrough

Input: s1 = "abab", s2 = "abc"

1. baseLCS = 2 (e.g. "ab").
2. Insert "c" at index 2 and match with p = 3 in s2.
3. lcsl[2][2] + lcsr[3][4] = 2 + 0 = 2 = baseLCS, so LCS becomes 3.
4. Same check succeeds for insertions at indices 3 and 4 with "c".

Output: 3

Common Pitfalls

• Use 1-based indices for lcsl/lcsr tables; insertion position i runs 0..n1.
• Break after the first valid p for each (i, c) — multiple p values must not double-count one insertion.
• Brute force (recompute LCS per insertion) times out on GFG; prefix/suffix DP is required.

Ways to Increase LCS by One.java

Java

// Approach: Precompute prefix LCS (lcsl) and suffix LCS (lcsr) tables. Inserting char c
// at position i in s1 increases LCS by 1 iff some position p in s2 with s2[p-1]==c satisfies
// lcsl[i][p-1] + lcsr[i+1][p+1] == baseLCS (prefix + inserted match + suffix).
// Time: O(n1 * n2) Space: O(n1 * n2)

import java.util.*;

class Solution {

    public int waysToIncreaseLCSBy1(String s1, String s2) {
        int n1 = s1.length();
        int n2 = s2.length();

        List<List<Integer>> positions = new ArrayList<>(26);
        for (int i = 0; i < 26; i++) {
            positions.add(new ArrayList<>());
        }
        for (int j = 1; j <= n2; j++) {
            positions.get(s2.charAt(j - 1) - 'a').add(j);
        }

        int[][] lcsl = new int[n1 + 2][n2 + 2];
        int[][] lcsr = new int[n1 + 2][n2 + 2];

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    lcsl[i][j] = lcsl[i - 1][j - 1] + 1;
                } else {
                    lcsl[i][j] = Math.max(lcsl[i - 1][j], lcsl[i][j - 1]);
                }
            }
        }

        for (int i = n1; i >= 1; i--) {
            for (int j = n2; j >= 1; j--) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    lcsr[i][j] = lcsr[i + 1][j + 1] + 1;
                } else {
                    lcsr[i][j] = Math.max(lcsr[i + 1][j], lcsr[i][j + 1]);
                }
            }
        }

        int base = lcsl[n1][n2];
        int ways = 0;

        for (int i = 0; i <= n1; i++) {
            for (int c = 0; c < 26; c++) {
                for (int p : positions.get(c)) {
                    if (lcsl[i][p - 1] + lcsr[i + 1][p + 1] == base) {
                        ways++;
                        break;
                    }
                }
            }
        }

        return ways;
    }
}

Was this solution helpful?