find longest common substring in space O(n) I am working on the class question find the longest common substring from 2 strings but I would like to return the longest common substring instead of just size of longest common substring.like

s1 = 'abcdex', s2 = 'xbcdey' =&gt; 'bcde'
s1 = 'abcxyx', s2 = 'xbcydey' =&gt; 'bc'



The way I do it is using dynamic programming to create a memo table and update each cell that required space \$O(n * m)\$. How can I implement the code so I can only using space as \$O(n)\$?

    def longestCommonSubstring(self, s1, s2):
        """
        :type s: str
        :rtype: str
        """
        m, n = len(s1), len(s2)
        dp = [[''] * (n + 1) for _ in range(m + 1)]
        max_len = ''
        for i, ic in enumerate(s1):
            for j, jc in enumerate(s2):
                dp[i][j] = dp[i - 1][j - 1] + ic if ic == jc else ''
                max_len = dp[i][j] if len(max_len) &lt; len(dp[i][j]) else max_len
        return max_len
PEP 8

You are following most of the PEP 8 style guidelines.  One that you are breaking is method names should be snake_case; your function should be named longest_common_substring.

Tricky Code

Your dp matrix is properly allocated to the size m+1 by n+1.

When you index your matrix, you access [i-1][j-1] with \$0 \le i \lt m\$ and \$0 \le j \lt n\$.  This means you never access the last allocated row m or the last allocated column n, but instead rely on accessing the -1 row and the -1 column wrapping around to reach these "unused" spaces.  This is "surprising" code at best, and "crashing" code if translated to a different programming language.

It would be better to add one to the indices used to index the dp matrix.  The simplest way would be to start the i and j enumerations at one:

    for i, ic in enumerate(s1, 1):
        for j, jc in enumerate(s2, 1):


Useless else

Expand out this ... if ... else ... statement:

            max_len = dp[i][j] if len(max_len) &lt; len(dp[i][j]) else max_len


Initially, this produces:

            if len(max_len) &lt; len(dp[i][j]):
                max_len = dp[i][j]
            else:
                max_len = max_len


But we can immediately see the else: clause is a no-op, and can be removed:

            if len(max_len) &lt; len(dp[i][j]):
                max_len = dp[i][j]


Which reads much more clearly than the original.

From \$O(n m)\$ to \$O(n)\$ space

During the first iteration of outer loop, you only access rows -1 and 0.  During the second iteration of outer loop, you only access rows 0 and 1.  During the third iteration of outer loop, you only access rows 1 and 2.  Etc.  You only need two rows of the dp matrix!

More over, you create the 0 row from the -1 row, you create the 1 from the 0 row, you create the 2 row from the 1 row, and so on.

Do you really need to keep the dp matrix?  Or could you use a previous_row and a current_row?  Only storing two length n rows reduces your space to \$O(2n)\$, which is simply \$O(n)\$.