Freestyle | The Longest Common Subsequence (LCS) | Java

devstromo · devstromo · commit db369fc74cd6 · 2025-05-16T22:28:25.000-03:00
diff --git a/freestyle/src/main/java/com/devstromo/dp/lcs/practice/with_k_skips/DESCRIPTION.md b/freestyle/src/main/java/com/devstromo/dp/lcs/practice/with_k_skips/DESCRIPTION.md
@@ -0,0 +1,43 @@
+# Longest Common Subsequence with Skips
+
+## Problem Statement
+
+Given two strings `text1` and `text2`, and an integer `k`, return the length of the **longest common subsequence** you
+can form **by skipping at most `k` characters in either string**. At any point, you may skip a character in `text1` or
+`text2` (but not both at the same time), and you can do this up to `k` times total.
+
+A subsequence of a string is a new string generated from the original string with some characters (possibly none)
+deleted without changing the relative order of the remaining characters.
+
+## Input
+
+- A string `text1` of length `n` (`1 <= n <= 1000`)
+- A string `text2` of length `m` (`1 <= m <= 1000`)
+- An integer `k` (`0 <= k <= min(n, m)`)
+
+## Output
+
+- An integer representing the length of the longest common subsequence obtainable by skipping at most `k` characters in
+  either `text1` or `text2`
+
+## Example
+
+### Input
+
+`text1 = "abcde"`
+`text2 = "acebd"`
+`k = 1`
+
+### Output
+3
+
+### Explanation
+
+The standard LCS is `"acd"` (length 3).  
+By skipping `'b'` from `text2`, we can align more characters and obtain the subsequence `"acd"` (length 3).
+
+## Constraints
+
+- `1 <= text1.length, text2.length <= 1000`
+- `0 <= k <= min(text1.length, text2.length)`
+- `text1` and `text2` consist of lowercase English letters only.
diff --git a/freestyle/src/main/java/com/devstromo/dp/lcs/practice/with_k_skips/Solution.java b/freestyle/src/main/java/com/devstromo/dp/lcs/practice/with_k_skips/Solution.java
@@ -0,0 +1,37 @@
+package com.devstromo.dp.lcs.practice.with_k_skips;
+
+public class Solution {
+    public int longestCommonSubsequenceWithSkips(String text1, String text2, int k) {
+        int n = text1.length();
+        int m = text2.length();
+        int[][][] dp = new int[n + 1][m + 1][k + 1];
+
+        for (int i = 0; i <= n; i++) {
+            for (int j = 0; j <= m; j++) {
+                for (int l = 0; l <= k; l++) {
+                    if (i == 0 || j == 0) {
+                        dp[i][j][l] = 0;
+                        continue;
+                    }
+                    if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
+                        dp[i][j][l] = dp[i - 1][j - 1][l] + 1;
+                    } else {
+                        int skipText1 = (l > 0) ? dp[i - 1][j][l - 1] : 0;
+                        int skipText2 = (l > 0) ? dp[i][j - 1][l - 1] : 0;
+                        dp[i][j][l] = Math.max(dp[i - 1][j][l], dp[i][j - 1][l]);
+                        if (l > 0) {
+                            dp[i][j][l] = Math.max(dp[i][j][l], Math.max(skipText1, skipText2));
+                        }
+                    }
+                }
+            }
+        }
+
+        int maxLCS = 0;
+        for (int l = 0; l <= k; l++) {
+            maxLCS = Math.max(maxLCS, dp[n][m][l]);
+        }
+        return maxLCS;
+    }
+
+}
diff --git a/freestyle/src/test/java/com/devstromo/dp/lcs/practice/with_k_skips/SolutionUnitTest.java b/freestyle/src/test/java/com/devstromo/dp/lcs/practice/with_k_skips/SolutionUnitTest.java
@@ -0,0 +1,58 @@
+package com.devstromo.dp.lcs.practice.with_k_skips;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class SolutionUnitTest {
+    private final Solution solver = new Solution();
+
+    @Test
+    void basicTest() {
+        String text1 = "abcde";
+        String text2 = "acebd";
+        int k = 1;
+        assertEquals(3, solver.longestCommonSubsequenceWithSkips(text1, text2, k));
+    }
+
+    @Test
+    void testNoSkipsSameAsLCS() {
+        String text1 = "abc";
+        String text2 = "abc";
+        int k = 0;
+        assertEquals(3, solver.longestCommonSubsequenceWithSkips(text1, text2, k));
+    }
+
+    @Test
+    void testWithSkipsImprovesLCS() {
+        String text1 = "abcxyz";
+        String text2 = "axyz";
+        int k = 1;
+        assertEquals(4, solver.longestCommonSubsequenceWithSkips(text1, text2, k));
+    }
+
+    @Test
+    void testEmptyString() {
+        String text1 = "";
+        String text2 = "abc";
+        int k = 2;
+        assertEquals(0, solver.longestCommonSubsequenceWithSkips(text1, text2, k));
+    }
+
+    @Test
+    void testSkipsUnused() {
+        String text1 = "abcdef";
+        String text2 = "acef";
+        int k = 3;
+        assertEquals(4, solver.longestCommonSubsequenceWithSkips(text1, text2, k));
+    }
+
+    @Test
+    void testAllSkipsNeeded() {
+        String text1 = "abc";
+        String text2 = "xyz";
+        int k = 3;
+        assertEquals(0, solver.longestCommonSubsequenceWithSkips(text1, text2, k));
+    }
+
+}
