Matrix DP

Overview

Two grid-shaped problems where the recurrence depends on the diagonal neighbour as well as the orthogonal ones. Longest common substring is LCS's stricter sibling: because the match must be contiguous, a mismatch resets the cell to zero rather than inheriting a neighbour. Largest square of 1s builds each cell from the minimum of its three neighbours — up, left and diagonal — because a square of side k can only sit here if all three of those directions already support side k-1. Both illustrate that the recurrence, not the table shape, encodes the problem's constraint.

Why it matters

Contiguity constraints appear whenever "a run" matters rather than "a selection": finding the longest shared code block between two files, the largest uniform region in an image, the biggest free rectangle in a bin-packing grid. The min of three neighbours is a small idea that shows up repeatedly in image processing and computational geometry on rasters.

Core concepts

Reset on mismatch. For longest common substring: dp[i][j] = (a[i-1] == b[j-1]) ? dp[i-1][j-1] + 1 : 0. The zero is the whole difference from LCS — a break in the match ends the run.

The answer is a running maximum. Because a substring may end anywhere, track best as you fill; the bottom-right cell is not the answer (unlike LCS).

Largest square recurrence. dp[i][j] = g[i][j] ? 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) : 0. The minimum is essential: the square is limited by its weakest supporting direction. Using max or omitting the diagonal reports squares that do not exist.

Why the diagonal matters. Up and left alone would permit an L-shaped region to masquerade as a square; the diagonal neighbour is what certifies the interior is filled.

Edges. Row 0 and column 0 of the square problem are simply the cell's own value (a 1 there supports at most a 1x1 square). A padded table with a zero border removes the special case entirely.

Answer units. The square DP stores side lengths; the area is best * best. Reporting the side when the area was wanted is a common slip.

Syntax notes

#include <stdlib.h>
#include <string.h>

/* longest common SUBSTRING (contiguous) */
int lcsub(const char *a, const char *b) {
    int la = (int)strlen(a), lb = (int)strlen(b), W = lb + 1, best = 0;
    int *dp = calloc((size_t)(la + 1) * W, sizeof *dp);
    if (!dp) return -1;
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++) {
            dp[i*W + j] = (a[i-1] == b[j-1]) ? dp[(i-1)*W + (j-1)] + 1 : 0;  /* RESET */
            if (dp[i*W + j] > best) best = dp[i*W + j];                      /* running max */
        }
    free(dp);
    return best;
}

/* largest square of 1s: dp holds SIDE lengths */
int msquare(const int *g, int r, int c) {
    int *dp = calloc((size_t)r * c, sizeof *dp), best = 0;
    if (!dp) return -1;
    for (int i = 0; i < r; i++)
        for (int j = 0; j < c; j++) {
            if (!g[i*c + j]) { dp[i*c + j] = 0; continue; }
            if (i == 0 || j == 0) dp[i*c + j] = 1;          /* edges: at most 1x1 */
            else {
                int u = dp[(i-1)*c + j], l = dp[i*c + (j-1)], d = dp[(i-1)*c + (j-1)];
                int m = (u < l) ? u : l; if (d < m) m = d;   /* MIN of three */
                dp[i*c + j] = m + 1;
            }
            if (dp[i*c + j] > best) best = dp[i*c + j];
        }
    free(dp);
    return best;
}

Key points:

• Substring resets to 0 on mismatch; subsequence does not.
• The square uses min of up, left and diagonal — all three.
• Both answers are running maxima, not the final cell.

Lesson

Two more 2-D DPs: longest common substring (contiguous, so a mismatch resets the run to 0) and maximal square (largest all-1 square, where a square grows only if all three neighbouring squares do). Both read each cell from its up, left, and diagonal neighbours.

Code examples

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
static int lcsub(const char*a,const char*b){int la=strlen(a),lb=strlen(b),W=lb+1,best=0;int*dp=calloc((la+1)*W,sizeof(int));for(int i=1;i<=la;i++)for(int j=1;j<=lb;j++)if(a[i-1]==b[j-1]){dp[i*W+j]=dp[(i-1)*W+j-1]+1;if(dp[i*W+j]>best)best=dp[i*W+j];}free(dp);return best;}
static int msquare(const int*g,int r,int c){int*dp=calloc((size_t)r*c,sizeof(int)),best=0;for(int i=0;i<r;i++)for(int j=0;j<c;j++)if(g[i*c+j]){if(i==0||j==0)dp[i*c+j]=1;else{int u=dp[(i-1)*c+j],l=dp[i*c+j-1],d=dp[(i-1)*c+j-1];int m=u<l?u:l;m=m<d?m:d;dp[i*c+j]=m+1;}if(dp[i*c+j]>best)best=dp[i*c+j];}free(dp);return best;}
int main(void){
    printf("longest common substring of \"GeeksforGeeks\",\"GeeksQuiz\" = %d\n", lcsub("GeeksforGeeks","GeeksQuiz"));
    int grid[]={1,0,1,0,0, 1,0,1,1,1, 1,1,1,1,1, 1,0,0,1,0};
    printf("largest all-1 square side = %d\n", msquare(grid,4,5));
    return 0;
}

Line by line

Common mistakes

Not resetting on a mismatch (common substring); taking max instead of min (maximal square).

Debugging tips

Compiler errors and warnings:

• -Wsign-compare from strlen; cast once.
• Nothing warns about max vs min in the square recurrence.

Runtime symptoms:

• Substring result equals the subsequence result. You inherited a neighbour on mismatch instead of resetting to 0.
• Substring answer is 0 despite an obvious match. You returned dp[la][lb] instead of the running maximum.
• Square DP reports squares that are not there. You used max instead of min, or omitted the diagonal neighbour — an L-shaped region then counts as a square.
• Off-by-one on the edges. Row 0 and column 0 must be the cell's own value; a padded border avoids the branch entirely.
• Area vs side confusion. dp holds side lengths; square it if the caller wants area.

Technique: for the square problem, hand-draw a 4x4 grid with an L-shape and confirm your code reports side 1 (or 2), not 3. That single case exposes both the min and the diagonal.

Memory safety

• Table size overflow. (la+1) * (lb+1) and r * c can overflow int; compute in size_t and bound the inputs.
• Stride discipline. W = lb + 1 for the string table but c for the grid — mixing them silently reads the wrong cells. Name the stride and use it consistently.
• Edge indexing. The square loop reads dp[(i-1)*c + j] only inside the else, guarded by i == 0 || j == 0; removing that guard produces negative indices.
• Zero-initialisation. calloc supplies the zero border and the reset semantics for free; malloc would leave garbage that the min would happily propagate.
• Grid contract. g must have exactly r*c elements; a mismatch between the caller's dimensions and the buffer is an out-of-bounds read the DP cannot detect.
• Free on all paths.

Real-world uses

Concrete uses: Longest common substring finds duplicated code blocks, shared file segments for deduplication, and plagiarism matches. The largest-square DP is used in image analysis to find uniform regions, in UI layout to fit the biggest square tile in a free area, and as a building block for maximal-rectangle algorithms in bin packing and floorplanning.

Professional best practices:

Beginner:

• Say out loud whether the problem needs contiguity; that single word picks the recurrence.
• Track the running maximum rather than reading the last cell.

Intermediate:

• Pad grids with a zero border to eliminate edge special-cases and the associated off-by-one bugs.
• The substring table can be reduced to two rows; the square table can be reduced to one row with careful bookkeeping of the diagonal.
• For maximal rectangles (not squares) use the histogram-stack technique — the square recurrence does not generalise.

Practice tasks

1. (Beginner) Longest common substring. Implement int lcsub(const char *a, const char *b). Example: "abcdxyz", "xyzabcd" -> 4. Concepts: reset on mismatch, running maximum.

2. (Beginner) Contrast with LCS. Run both LCS and LCSubstring on the same pair and explain the difference. Example: the pair above gives 4 either way; find a pair where they differ. Concepts: contiguity.

3. (Intermediate) Largest square. Implement int msquare(const int *g, int r, int c) returning the side length. Example: a grid whose largest solid block is 3x3 -> 3. Concepts: min of three neighbours.

4. (Intermediate) Report position and area. Extend the square DP to return the area and the bottom-right coordinate of the best square. Concepts: tracking provenance, side vs area.

Summary

Both problems are grid DPs whose recurrence encodes a contiguity constraint. Longest common substring resets a cell to zero on mismatch — that single difference from LCS is what enforces contiguity — and the answer is a running maximum, not the final cell. The largest-square DP stores side lengths and takes 1 + min(up, left, diagonal), where the minimum and the diagonal together are what prevent an L-shaped region from being counted as a square. Pad the borders or guard the edges, keep your strides straight, and remember the table holds sides while the caller may want area.

Practice with these exercises

• Longest common substring
• Maximal square