Significance:
Global alignment forces two sequences to line up end to end, which is wrong whenever you're looking for a shared domain inside otherwise unrelated proteins. Smith-Waterman finds the best-scoring *local* region instead, and that single change — clamping negative scores to zero — is what makes database search possible. BLAST is a fast heuristic for exactly this.
Statement
Compute the **optimal local alignment score** of two DNA strings using the Smith-Waterman algorithm.
Scoring:
- match: `+2` - mismatch: `-1` - gap (linear, each gap character): `-2`
Unlike global alignment, any cell whose score would go negative is set to `0`, and the answer is the maximum value anywhere in the matrix. The two strings arrive on two separate lines.
Print a single integer: the maximum local alignment score.
*(Only the score is required — several distinct local alignments can tie for the optimum, so an alignment string could not be graded unambiguously.)*
Input — read from standard input
Variable
Type
Description
a
line 1
str
The first sequence
1 <= len(a) <= 200, uppercase A, C, G, T only
b
line 2
str
The second sequence
1 <= len(b) <= 200
These variables are already read for you in the starter code on the right.
Output
int
the maximum local alignment score, as a single integer
Sample Cases
Sample 1
Input
TGTTACGG
GGTTGACTA
Expected Output
8
The best local region is GTT-AC against GTTGAC, scoring 8.
Sample 2
Input
AAAA
TTTT
Expected Output
0
Nothing aligns positively, so the clamped score is 0.
Submit also runs your code against 4 hidden test cases.
Hidden inputs are never shown — if one fails you'll get its number and a description of the
mismatch, not the data.
Constraints
- `1 <= length(a), length(b) <= 200` - match `+2`, mismatch `-1`, gap `-2` - Scores are clamped at `0`, so the answer is never negative
- The recurrence is the same as Needleman-Wunsch with one extra `0` in the `max()`. - Track the running maximum as you fill the matrix rather than scanning it again at the end.
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...