# Longest Common Substring (Space optimized DP solution)

Given two strings ‘X’ and ‘Y’, find the length of longest common substring. Expected space complexity is linear.

Examples :

```Input : X = "GeeksforGeeks", Y = "GeeksQuiz"
Output : 5
The longest common substring is "Geeks" and is of
length 5.

Input : X = "abcdxyz", Y = "xyzabcd"
Output : 4
The longest common substring is "abcd" and is of
length 4.
``` ## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We have discussed Dynamic programming based solution for Longest common substring. The auxiliary space used by the solution is O(m*n), where m and n are lengths of string X and Y. The space used by solution can be reduced to O(2*n).
Suppose we are at position mat[i][j]. Now if X[i-1] == Y[j-1], then we add the value of mat[i-1][j-1] to our result. That is we add value from previous row and value for all other rows below the previous row are never used. So, at a time we are using only two consecutive rows. This observation can be used to reduce the space required to find length of longest common substring.
Instead of creating a matrix of size m*n, we create a matrix of size 2*n. A variable currRow is used to represent that either row 0 or row 1 of this matrix is currently used to find length. Initially row 0 is used as current row for the case when length of string X is zero. At the end of each iteration, current row is made previous row and previous row is made new current row.

## C++

 `// Space optimized CPP implementation of longest ` `// common substring. ` `#include ` `using` `namespace` `std; ` ` `  `// Function to find longest common substring. ` `int` `LCSubStr(string X, string Y) ` `{ ` `    ``// Find length of both the strings. ` `    ``int` `m = X.length(); ` `    ``int` `n = Y.length(); ` ` `  `    ``// Variable to store length of longest ` `    ``// common substring. ` `    ``int` `result = 0; ` ` `  `    ``// Matrix to store result of two ` `    ``// consecutive rows at a time. ` `    ``int` `len[n]; ` ` `  `    ``// Variable to represent which row of ` `    ``// matrix is current row. ` `    ``int` `currRow = 0; ` ` `  `    ``// For a particular value of i and j, ` `    ``// len[currRow][j] stores length of longest ` `    ``// common substring in string X[0..i] and Y[0..j]. ` `    ``for` `(``int` `i = 0; i <= m; i++) { ` `        ``for` `(``int` `j = 0; j <= n; j++) { ` `            ``if` `(i == 0 || j == 0) { ` `                ``len[currRow][j] = 0; ` `            ``} ` `            ``else` `if` `(X[i - 1] == Y[j - 1]) { ` `                ``len[currRow][j] = len[1 - currRow][j - 1] + 1; ` `                ``result = max(result, len[currRow][j]); ` `            ``} ` `            ``else` `{ ` `                ``len[currRow][j] = 0; ` `            ``} ` `        ``} ` ` `  `        ``// Make current row as previous row and previous ` `        ``// row as new current row. ` `        ``currRow = 1 - currRow; ` `    ``} ` ` `  `    ``return` `result; ` `} ` ` `  `int` `main() ` `{ ` `    ``string X = ``"GeeksforGeeks"``; ` `    ``string Y = ``"GeeksQuiz"``; ` ` `  `    ``cout << LCSubStr(X, Y); ` `    ``return` `0; ` `} `

## Java

 `// Space optimized CPP implementation of  ` `// longest common substring. ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `public` `class` `GFG { ` `     `  `    ``// Function to find longest ` `    ``// common substring. ` `    ``static` `int` `LCSubStr(String X, String Y) ` `    ``{ ` `         `  `        ``// Find length of both the strings. ` `        ``int` `m = X.length(); ` `        ``int` `n = Y.length(); ` `     `  `        ``// Variable to store length of longest ` `        ``// common substring. ` `        ``int` `result = ``0``; ` `     `  `        ``// Matrix to store result of two ` `        ``// consecutive rows at a time. ` `        ``int` `[][]len = ``new` `int``[``2``][n]; ` `     `  `        ``// Variable to represent which row of ` `        ``// matrix is current row. ` `        ``int` `currRow = ``0``; ` `     `  `        ``// For a particular value of ` `        ``// i and j, len[currRow][j]  ` `        ``// stores length of longest ` `        ``// common substring in string ` `        ``// X[0..i] and Y[0..j]. ` `        ``for` `(``int` `i = ``0``; i < m; i++) { ` `            ``for` `(``int` `j = ``0``; j < n; j++) { ` `                ``if` `(i == ``0` `|| j == ``0``) { ` `                    ``len[currRow][j] = ``0``; ` `                ``} ` `                ``else` `if` `(X.charAt(i - ``1``) ==  ` `                              ``Y.charAt(j - ``1``)) ` `                ``{ ` `                    ``len[currRow][j] = ` `                      ``len[(``1` `- currRow)][(j - ``1``)] ` `                                             ``+ ``1``; ` `                    ``result = Math.max(result,  ` `                                ``len[currRow][j]); ` `                ``} ` `                ``else` `                ``{ ` `                    ``len[currRow][j] = ``0``; ` `                ``} ` `            ``} ` `     `  `            ``// Make current row as previous ` `            ``// row and previous row as  ` `            ``// new current row. ` `            ``currRow = ``1` `- currRow; ` `        ``} ` `     `  `        ``return` `result; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``String X = ``"GeeksforGeeks"``; ` `        ``String Y = ``"GeeksQuiz"``; ` `     `  `        ``System.out.print(LCSubStr(X, Y)); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw (manishshaw1) `

/div>

## Python3

 `# Space optimized Python3 implementation   ` `# of longest common substring.  ` `import` `numpy as np ` ` `  `# Function to find longest common substring.  ` `def` `LCSubStr(X, Y) :  ` ` `  `    ``# Find length of both the strings.  ` `    ``m ``=` `len``(X)  ` `    ``n ``=` `len``(Y)  ` ` `  `    ``# Variable to store length of  ` `    ``# longest common substring.  ` `    ``result ``=` `0` ` `  `    ``# Matrix to store result of two  ` `    ``# consecutive rows at a time.  ` `    ``len_mat ``=` `np.zeros((``2``, n))  ` ` `  `    ``# Variable to represent which row   ` `    ``# of matrix is current row.  ` `    ``currRow ``=` `0` ` `  `    ``# For a particular value of i and j,  ` `    ``# len_mat[currRow][j] stores length of  ` `    ``# longest common substring in string  ` `    ``# X[0..i] and Y[0..j].  ` `    ``for` `i ``in` `range``(m) :  ` `        ``for` `j ``in` `range``(n) : ` `                         `  `            ``if` `(i ``=``=` `0` `| j ``=``=` `0``) :  ` `                ``len_mat[currRow][j] ``=` `0` `             `  `            ``elif` `(X[i ``-` `1``] ``=``=` `Y[j ``-` `1``]) : ` `                                 `  `                ``len_mat[currRow][j] ``=` `len_mat[``1` `-` `currRow][j ``-` `1``] ``+` `1` `                ``result ``=` `max``(result, len_mat[currRow][j]) ` `             `  `            ``else` `:  ` `                ``len_mat[currRow][j] ``=` `0` `             `  `        ``# Make current row as previous row and  ` `        ``# previous row as new current row.  ` `        ``currRow ``=` `1` `-` `currRow ` ` `  `    ``return` `result ` ` `  `# Driver Code ` `if` `__name__ ``=``=` `"__main__"` `:  ` ` `  `    ``X ``=` `"GeeksforGeeks"` `    ``Y ``=` `"GeeksQuiz"` ` `  `    ``print``(LCSubStr(X, Y)) ` ` `  `# This code is contributed by Ryuga `

## C#

 `// Space optimized C# implementation ` `// of longest common substring. ` `using` `System; ` `using` `System.Collections.Generic; ` `class` `GFG { ` `     `  `    ``// Function to find longest ` `    ``// common substring. ` `    ``static` `int` `LCSubStr(``string` `X, ``string` `Y) ` `    ``{ ` `         `  `        ``// Find length of both the strings. ` `        ``int` `m = X.Length; ` `        ``int` `n = Y.Length; ` `     `  `        ``// Variable to store length of longest ` `        ``// common substring. ` `        ``int` `result = 0; ` `     `  `        ``// Matrix to store result of two ` `        ``// consecutive rows at a time. ` `        ``int` `[,]len = ``new` `int``[2,n]; ` `     `  `        ``// Variable to represent which row of ` `        ``// matrix is current row. ` `        ``int` `currRow = 0; ` `     `  `        ``// For a particular value of ` `        ``// i and j, len[currRow][j]  ` `        ``// stores length of longest ` `        ``// common substring in string ` `        ``// X[0..i] and Y[0..j]. ` `        ``for` `(``int` `i = 0; i < m; i++) { ` `            ``for` `(``int` `j = 0; j < n; j++) { ` `                ``if` `(i == 0 || j == 0) { ` `                    ``len[currRow,j] = 0; ` `                ``} ` `                ``else` `if` `(X[i - 1] == Y[j - 1]) { ` `                    ``len[currRow,j] = len[(1 - currRow),  ` `                                          ``(j - 1)] + 1; ` `                    ``result = Math.Max(result, len[currRow, j]); ` `                ``} ` `                ``else`  `                ``{ ` `                    ``len[currRow,j] = 0; ` `                ``} ` `            ``} ` `     `  `            ``// Make current row as previous ` `            ``// row and previous row as  ` `            ``// new current row. ` `            ``currRow = 1 - currRow; ` `        ``} ` `     `  `        ``return` `result; ` `    ``} ` `     `  `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``string` `X = ``"GeeksforGeeks"``; ` `        ``string` `Y = ``"GeeksQuiz"``; ` `     `  `        ``Console.Write(LCSubStr(X, Y)); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw (manishshaw1) `

## PHP

 ` `

Output :

```5
```

Time Complexity: O(m*n)
Auxiliary Space: O(n)