Longest Common Substring
Learn Longest Common Substring (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
The One Key Difference from LCS Longest Common Substring requires CONTIGUOUS matching characters. The DP recurrence is almost identical to LCS, but on a mismatch, dp[i][j] RESETS to 0 (instead of taking the max of neighbors) - a broken match must start completely over, since a substring can't have gaps.
More lessons in Dynamic Programming
- Fibonacci (DP)
- Climbing Stairs
- House Robber
- Kadane (DP)
- Grid Paths
- Unique Paths
- Minimum Path Sum
- 0/1 Knapsack
- Unbounded Knapsack
- Bounded Knapsack
- Subset Sum
- Equal Partition
- Target Sum
- Longest Common Subsequence - LCS
- Edit Distance
- Longest Palindromic Subsequence
- Palindrome Partitioning
- Longest Increasing Subsequence - LIS
- Number of LIS
- Maximum Sum Increasing Subsequence
- Matrix Chain Multiplication
- Burst Balloons
- Optimal BST
- Diameter (Tree DP)
- Maximum Path Sum (Tree DP)
- Tree Independent Set
- Traveling Salesman Problem
- Assignment Problems
- Counting Numbers (Digit DP)
- Digit Constraints