Problem Statement
You are given two strings:
s1 of length n
s2 of length m
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
s1 = "abab"
s2 = "abc"
Output
3
Possible insertions are:
Each of them increases the LCS from 2 to 3.
Observation
Suppose the original LCS is:
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:
L + 1
Brute Force Approach
For every insertion position:
0...n
Try every character:
'a' ... 'z'
Create the new string.
Compute the LCS again.
Count if:
newLCS == oldLCS + 1
Complexity
Positions: (n + 1)
Characters: 26
LCS: O(n × m)
Total:
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:
pre[i][j]
denote:
LCS of
s1[0...i-1]
and
s2[0...j-1]
For example:
s1 = abab
s2 = abc
pre[2][2]
means:
ab
ab
LCS = 2
Transition
If characters match:
pre[i][j]
=
pre[i-1][j-1] + 1
Otherwise:
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:
suf[i][j]
mean:
LCS of
s1[i...]
and
s2[j...]
Example
s1 = abab
s2 = abc
suf[2][1]
means:
ab
bc
Again:
If characters match:
suf[i][j]
=
1 + suf[i+1][j+1]
Else:
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.
Left Part | Inserted Character | Right Part
Example:
ab|X|ab
If X matches s2[j], then:
Left side contributes:
pre[i][j]
The inserted character contributes:
1
The remaining suffix contributes:
suf[i][j+1]
Therefore:
Total LCS
=
pre[i][j]
+
1
+
suf[i][j+1]
If this becomes:
originalLCS + 1
then this insertion is valid.
Formula
The key formula is:
pre[i][j]
+
1
+
suf[i][j+1]
==
originalLCS + 1
If true, then inserting:
s2[j]
at position:
i
will increase the LCS by exactly one.
Why j + 1?
Suppose:
s2
A B C D
^
matched character
Once the inserted character matches:
C
the remaining suffix should begin after C.
Hence:
j + 1
Why Boolean Array?
Suppose:
s2 = aaa
All three positions represent inserting the same character 'a' at the same insertion position.
We should count:
(position, 'a')
only once.
So for every insertion position we use:
boolean[] used = new boolean[26];
Once 'a' is counted, we never count it again for that position.
Dry Run
s1 = abab
s2 = abc
Original:
LCS = 2
Try inserting at position:
2
ab| |ab
Try matching:
s2[2] = 'c'
Suppose:
pre[2][2] = 2
and:
suf[2][3] = 0
Then:
2 + 1 + 0 = 3
Original:
2
New:
3
Valid insertion.
Code Explanation
Prefix DP
int[][] pre = new int[n + 1][m + 1];
Stores prefix LCS values.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
Fill the table.
If Characters Match
if (s1.charAt(i - 1) == s2.charAt(j - 1))
pre[i][j] = pre[i - 1][j - 1] + 1;
We extend the LCS.
Otherwise
else
pre[i][j] = Math.max(pre[i - 1][j], pre[i][j - 1]);
Take the better of skipping one character.
Suffix DP
int[][] suf = new int[n + 1][m + 1];
Stores suffix LCS.
Filled backwards.
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
If Characters Match
suf[i][j] = suf[i + 1][j + 1] + 1;
Else
suf[i][j] =
Math.max(
suf[i + 1][j],
suf[i][j + 1]
);
Original LCS
int lcs = pre[n][m];
The final value of the prefix DP is the LCS of the entire strings.
Try Every Insertion Position
for (int i = 0; i <= n; i++) {
There are:
n + 1
possible insertion positions.
Example:
_ a _ b _ c _
Avoid Duplicate Characters
boolean[] used = new boolean[26];
Prevents counting the same inserted character multiple times at the same position.
Try Every Character Already Present in s2
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
if (!used[ch] &&
pre[i][j] + 1 + suf[i][j + 1] == lcs + 1)
This checks whether:
The left prefixes can contribute pre[i][j].
The inserted character contributes 1.
The remaining suffixes contribute suf[i][j + 1].
If their sum equals originalLCS + 1, the insertion is valid.
Count Answer
used[ch] = true;
ans++;
Mark the character as counted for this position and increment the result.
Complete Complexity Analysis
Time Complexity
Building prefix DP:
O(n × m)
Building suffix DP:
O(n × m)
Checking every insertion:
(n + 1) × m
O(n × m)
Overall:
O(n × m)
Space Complexity
Two DP tables:
pre
suf
Each requires:
O(n × m)
So the total auxiliary space is:
O(n × m)
Complete Java Solution
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
Compute the prefix LCS (pre) and suffix LCS (suf) only once.
For every insertion position, test matches against characters in s2 using the formula:
pre[i][j] + 1 + suf[i][j + 1] == originalLCS + 1
Use a boolean[26] array to avoid counting the same character more than once at the same insertion position.
This reduces the solution from repeatedly recomputing LCS to an efficient O(n × m) dynamic programming algorithm.
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.