Pattern: String difference counting / brute-force with pruning
You are given n strings, each of length m, consisting only of lowercase letters.
Your task is to choose two strings such that the total absolute difference between corresponding characters is minimum.
Character difference is computed as:
abs(s1[i] – s2[i]) for each index i.
Return the minimum possible sum.
For every pair of strings, compare them character-by-character and compute the total difference.
Since n ≤ 50 and m ≤ 50, brute force over all pairs is fast enough (around 1225 comparisons max).
n m
s₁
s₂
…
sₙ
Minimum total difference across all pairs.
Input:
3 3
abc
bcd
bbb
Output:
3
Explanation:
Compare each pair:
abc vs bcd → |a-b| + |b-c| + |c-d| = 1+1+1 = 3
abc vs bbb → |a-b| + |b-b| + |c-b| = 1+0+1 = 2
bcd vs bbb → |b-b| + |c-b| + |d-b| = 0+1+2 = 3
Minimum = 2.
-
2 ≤ n ≤ 50
-
1 ≤ m ≤ 50
-
Strings contain only lowercase letters
-
Compare all pairs (i, j)
-
For each pair, compute sum of absolute differences
-
Track global minimum
Since constraints are small, brute-force is optimal.
The main idea is to compute distances efficiently and update the minimum.