## Intuition The problem requires finding the minimum difference between any two words from a given list, where the difference is defined as the sum of the absolute differences of corresponding characters in the two words. Given the constraints, a brute force approach is feasible. We can calculate the difference for every possible pair of words and find the minimum. ## Approach 1. **Input Parsing:** Start by reading the number of test cases. For each test case, read the number of words `n` and their length `m`, followed by the `n` words. 2. **Pairwise Comparison:** For each pair of words `(s_i, s_j)` where `i < j`, calculate the difference: - For each character position `k` in the words, compute the absolute difference `|s_i[k] - s_j[k]|`. - Sum these differences to get the total difference for the pair. 3. **Track Minimum Difference:** Keep track of the minimum difference encountered for each test case. 4. **Output the Results:** After processing all pairs for a test case, output the minimum difference. ## Complexity - **Time Complexity:** \(O(t \times n^2 \times m)\), where \(t\) is the number of test cases, \(n\) is the number of words, and \(m\) is the length of each word. This is efficient given the constraints. - **Space Complexity:** \(O(n \times m)\) for storing the words, which is manageable within the given limits. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n, m; cin >> n >> m; vector words(n); for (int i = 0; i < n; ++i) { cin >> words[i]; } int min_difference = INT_MAX; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { int current_difference = 0; for (int k = 0; k < m; ++k) { current_difference += abs(words[i][k] - words[j][k]); } min_difference = min(min_difference, current_difference); } } cout << min_difference << '\n'; } return 0; } ``` This solution efficiently computes the minimum difference for each test case by examining all possible pairs of words and calculating their differences character by character. The use of `abs` ensures that we correctly compute the absolute difference between characters, and the nested loops handle all pairwise comparisons.

Most Similar Words

Problem Details