Longest Common Substring

GeeksforGeeks

Step-by-Step Solution Approach: Longest Common Substring

Finding the longest common substring between two strings is a classic problem in dynamic programming. Let's break down the solution step by step:

Problem Statement:

Given two strings str1 and str2, find the length of the longest common substring. A substring is a contiguous sequence of characters within a string.

Approach: Dynamic Programming

1. Initialize a 2D DP Table:

• Create a 2D table dp where dp[i][j] will store the length of the longest common substring ending at str1[i-1] and str2[j-1].
• The dimensions of the dp table will be (len(str1) + 1) x (len(str2) + 1).

1. Filling the DP Table:

• If the characters str1[i-1] and str2[j-1] match, then the value of dp[i][j] will be dp[i-1][j-1] + 1.
• If they don't match, set dp[i][j] to 0 because the common substring breaks.

1. Tracking the Maximum Length:

• Keep track of the maximum value in the dp table. This value will be the length of the longest common substring.

1. Return the Result:

• After filling the table, the maximum value found in the table is the length of the longest common substring.

Java Implementation:

Explanation of the Code:

• Initialization: We first initialize the dp table and a variable maxLength to track the length of the longest common substring.
• Nested Loops: We use two nested loops to iterate over every character pair in str1 and str2.
• Character Matching: If the characters match, we update dp[i][j] to be dp[i-1][j-1] + 1, meaning we extend the previous common substring by one character.
• Result: Finally, we return the maximum value found in the dp table.

Time Complexity:

• The time complexity of this solution is O(n * m), where n is the length of str1 and m is the length of str2.

Space Complexity:

• The auxiliary space complexity is also O(n * m) due to the dp table.

Conclusion:

This dynamic programming approach efficiently finds the length of the longest common substring between two strings. It's a classic example of how dynamic programming can be applied to solve problems involving substrings and subsequences.

GITHUB:

SMILE_KHAN-JAVA+PYTHON

#Java #DynamicProgramming #ProblemSolving #LongestCommonSubstring #CodeOfTheDay #ProgrammingTips #LinkedInLearning