Longest Common Substring — Solution & Editorial | Jobs at Avian IT

Hiring process8 levels

1 IQ Test
2 Additional Online Test (If Required)
3 Office Interview with Hiring Manager
4 Unpaid Test Task (Motivation Check)
5 Paid Test Task and Follow-Up Interview
6 Iterative Paid Test Tasks
7 Office Verification
8 Final Interview with the Founder

Problems > Longest Common Substring > Editorial

Longest Common Substring — Solution & Editorial

Back to the Problem

dp[i][j] = common suffix length ending at A_i, B_j: extend on match, reset to 0 otherwise (unlike LCS, no carrying over).

Complexity: O(|A|·|B|)

Watch out: Substring ≠ subsequence: the max(...) carry-over from LCS must NOT be here.