Problem Statement

You are given two strings:

You must insert exactly one lowercase character into s1.

Your task is to count the number of different insertions (position + character) such that the Longest Common Subsequence (LCS) of the two strings increases by exactly one.

Example

Input

Code
s1 = "abab"
s2 = "abc"

Output

Code
3

Possible insertions are:

Each of them increases the LCS from 2 to 3.

Observation

Suppose the original LCS is:

Code
L

After inserting one character, the maximum possible increase is only 1 because we are adding only one character.

So we only need to check whether an insertion makes the LCS become:

Code
L + 1

Brute Force Approach

For every insertion position:

Code
0...n

Try every character:

Code
'a' ... 'z'

Create the new string.

Compute the LCS again.

Count if:

Code
newLCS == oldLCS + 1

Complexity

Total:

Code
O(26 × n² × m)

This is far too slow.

Optimized Dynamic Programming

Instead of recomputing LCS every time, we precompute information.

We build two DP tables.

Step 1: Prefix LCS

Let:

Code
pre[i][j]

denote:

Code
LCS of

s1[0...i-1]
and
s2[0...j-1]

For example:

Code
s1 = abab
s2 = abc
Code
pre[2][2]

means:

Code
ab
ab

LCS = 2

Transition

If characters match:

Code
pre[i][j]
=
pre[i-1][j-1] + 1

Otherwise:

Code
pre[i][j]
=
max(pre[i-1][j], pre[i][j-1])

This is the standard LCS DP.

Step 2: Suffix LCS

Now compute LCS from the back.

Let:

Code
suf[i][j]

mean:

Code
LCS of

s1[i...]
and
s2[j...]

Example

Code
s1 = abab
s2 = abc
Code
suf[2][1]

means:

Code
ab
bc

Again:

If characters match:

Code
suf[i][j]
=
1 + suf[i+1][j+1]

Else:

Code
max(
    suf[i+1][j],
    suf[i][j+1]
)

This DP is filled from bottom-right to top-left.

Why Prefix and Suffix?

Suppose we insert a character at position i.

Code
Left Part | Inserted Character | Right Part

Example:

Code
ab|X|ab

If X matches s2[j], then:

Left side contributes:

Code
pre[i][j]

The inserted character contributes:

Code
1

The remaining suffix contributes:

Code
suf[i][j+1]

Therefore:

Code
Total LCS

=
pre[i][j]
+
1
+
suf[i][j+1]

If this becomes:

Code
originalLCS + 1

then this insertion is valid.

Formula

The key formula is:

Code
pre[i][j]
+
1
+
suf[i][j+1]
==
originalLCS + 1

If true, then inserting:

Code
s2[j]

at position:

Code
i

will increase the LCS by exactly one.

Why j + 1?

Suppose:

Code
s2

A B C D
      ^
      matched character

Once the inserted character matches:

Code
C

the remaining suffix should begin after C.

Hence:

Code
j + 1

Why Boolean Array?

Suppose:

Code
s2 = aaa

All three positions represent inserting the same character 'a' at the same insertion position.

We should count:

Code
(position, 'a')

only once.

So for every insertion position we use:

Java
boolean[] used = new boolean[26];

Once 'a' is counted, we never count it again for that position.

Dry Run

Code
s1 = abab
s2 = abc

Original:

Code
LCS = 2

Try inserting at position:

Code
2
Code
ab| |ab

Try matching:

Code
s2[2] = 'c'

Suppose:

Code
pre[2][2] = 2

and:

Code
suf[2][3] = 0

Then:

Code
2 + 1 + 0 = 3

Original:

Code
2

New:

Code
3

Valid insertion.

Code Explanation

Prefix DP

Java
int[][] pre = new int[n + 1][m + 1];

Stores prefix LCS values.

Java
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {

Fill the table.

If Characters Match

Java
if (s1.charAt(i - 1) == s2.charAt(j - 1))
    pre[i][j] = pre[i - 1][j - 1] + 1;

We extend the LCS.

Otherwise

Java
else
    pre[i][j] = Math.max(pre[i - 1][j], pre[i][j - 1]);

Take the better of skipping one character.

Suffix DP

Java
int[][] suf = new int[n + 1][m + 1];

Stores suffix LCS.

Filled backwards.

Java
for (int i = n - 1; i >= 0; i--) {
    for (int j = m - 1; j >= 0; j--) {

If Characters Match

Java
suf[i][j] = suf[i + 1][j + 1] + 1;

Else

Java
suf[i][j] =
Math.max(
    suf[i + 1][j],
    suf[i][j + 1]
);

Original LCS

Java
int lcs = pre[n][m];

The final value of the prefix DP is the LCS of the entire strings.

Try Every Insertion Position

Java
for (int i = 0; i <= n; i++) {

There are:

Code
n + 1

possible insertion positions.

Example:

Code
_ a _ b _ c _

Avoid Duplicate Characters

Java
boolean[] used = new boolean[26];

Prevents counting the same inserted character multiple times at the same position.

Try Every Character Already Present in s2

Java
for (int j = 0; j < m; j++) {

If we want the inserted character to contribute to the LCS, it must match some character in s2. Therefore, we only need to consider characters from s2.

Core Condition

Java
if (!used[ch] &&
    pre[i][j] + 1 + suf[i][j + 1] == lcs + 1)

This checks whether:

If their sum equals originalLCS + 1, the insertion is valid.

Count Answer

Java
used[ch] = true;
ans++;

Mark the character as counted for this position and increment the result.

Complete Complexity Analysis

Time Complexity

Building prefix DP:

Code
O(n × m)

Building suffix DP:

Code
O(n × m)

Checking every insertion:

Code
(n + 1) × m
Code
O(n × m)

Overall:

Code
O(n × m)

Space Complexity

Two DP tables:

Code
pre
suf

Each requires:

Code
O(n × m)

So the total auxiliary space is:

Code
O(n × m)

Complete Java Solution

Java
class Solution {

    public int waysToIncreaseLCSBy1(String s1, String s2) {

        int n = s1.length();
        int m = s2.length();

        // -----------------------------
        // Prefix LCS DP
        // pre[i][j] = LCS of
        // s1[0...i-1] and s2[0...j-1]
        // -----------------------------
        int[][] pre = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {

            for (int j = 1; j <= m; j++) {

                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

                    pre[i][j] = pre[i - 1][j - 1] + 1;

                } else {

                    pre[i][j] = Math.max(pre[i - 1][j], pre[i][j - 1]);

                }

            }

        }

        // Original LCS
        int lcs = pre[n][m];

        // -----------------------------
        // Suffix LCS DP
        // suf[i][j] = LCS of
        // s1[i...n-1] and s2[j...m-1]
        // -----------------------------
        int[][] suf = new int[n + 1][m + 1];

        for (int i = n - 1; i >= 0; i--) {

            for (int j = m - 1; j >= 0; j--) {

                if (s1.charAt(i) == s2.charAt(j)) {

                    suf[i][j] = 1 + suf[i + 1][j + 1];

                } else {

                    suf[i][j] = Math.max(suf[i + 1][j], suf[i][j + 1]);

                }

            }

        }

        int ans = 0;

        // -----------------------------------
        // Try every insertion position
        // There are n+1 possible positions.
        // -----------------------------------
        for (int i = 0; i <= n; i++) {

            // Avoid counting the same character
            // more than once at this position.
            boolean[] used = new boolean[26];

            // Try matching every character of s2
            for (int j = 0; j < m; j++) {

                int ch = s2.charAt(j) - 'a';

                // Formula:
                // pre[i][j] + 1 + suf[i][j+1]
                //
                // left LCS
                // + inserted character
                // + right LCS
                //
                // If it becomes original LCS + 1,
                // then this insertion is valid.
                if (!used[ch] &&
                    pre[i][j] + 1 + suf[i][j + 1] == lcs + 1) {

                    used[ch] = true;

                    ans++;

                }

            }

        }

        return ans;

    }

}

Key Takeaways

Code
pre[i][j] + 1 + suf[i][j + 1] == originalLCS + 1

Summary

To count insertions that increase the LCS by exactly one, we precompute prefix and suffix LCS tables and evaluate each insertion position using the formula pre[i][j] + 1 + suf[i][j + 1]. By avoiding repeated LCS calculations and eliminating duplicate character counts with a boolean array, the solution achieves an efficient time complexity of O(n × m) and is well suited for large input sizes.