Overview
Hamming Distance is a simple fixed-position difference measure for equal-length sequences.
CoreSource checked
Hamming Distance
Counts positions where two equal-length strings or vectors differ.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Beginner
- Family
- Distance Metric
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
aligned comparisonmismatch countfixed lengthdistance metric
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use when sequences are the same length and positions are already aligned.
- Use when error detection is a central requirement.
When Not to Use
- Avoid when insertions, deletions, or timing shifts should be allowed.
- Avoid when the distance or match rule does not reflect the real similarity question.
What It Does
- Compares aligned positions
- Counts mismatches
- Returns a distance score
Use Cases
- Error detection
- Binary code comparison
- Fixed-length string similarity
Inputs
- Two equal-length sequences
Outputs
- Mismatch count
Key Formulas (1)
Mismatch count
distance = count(i where a[i] ≠ b[i])
distance = count(i where a[i] != b[i])Counts aligned positions with different symbols.
Pseudocode
- 1.Check that the sequences have the same length
- 2.Set count to zero
- 3.Compare each aligned position
- 4.Increment count for every mismatch
- 5.Return count
Canonical Example
- Input
- a = "10110", b = "10011"
- Output
- distance = 2
- Explanation
- The strings differ at two aligned positions.
Implementation Notes
- For bit vectors, XOR then count set bits for a fast implementation.
- Test exact match, no match, repeated characters, and empty input cases.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Silently comparing unequal lengths hides missing or extra symbols.
- Indexing and empty-pattern cases often cause off-by-one errors.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow two aligned strings with mismatched positions highlighted.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Check that the sequences have the same length
sequence-matchNotes
For unequal-length sequences, edit distance is usually a better fit.
Sources (1)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference covering Hamming Distance recurrences, automata/indexing structures, or exact/approximate matching role.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toJaro-Winkler Distance
Both score string similarity with different assumptions.
SpecializesLevenshtein Distance
Hamming distance compares substitutions only for equal-length strings.
Related Algorithms
Tags
Pattern MatchingStringsEdit Distance