You are given a string array words.
Find the maximum distance between two distinct indices i and j such that:
words[i] != words[j], andj - i + 1.Return the maximum distance among all such pairs. If no valid pair exists, return 0.
Example 1:
Input: words = ["leetcode","leetcode","codeforces"]
Output: 3
Explanation:
In this example, words[0] and words[2] are not equal, and they have the maximum distance 2 - 0 + 1 = 3.
Example 2:
Input: words = ["a","b","c","a","a"]
Output: 4
Explanation:
In this example words[1] and words[4] have the largest distance of 4 - 1 + 1 = 4.
Example 3:
Input: words = ["z","z","z"]
Output: 0
Explanation:
In this example all the words are equal, thus the answer is 0.
Constraints:
1 <= words.length <= 1051 <= words[i].length <= 10words[i] consists of lowercase English letters.Problem Overview: Given an array of words, return the maximum distance |i - j| such that words[i] != words[j]. The goal is to find the farthest pair of indices containing different strings.
Approach 1: Brute Force Pair Check (O(n²) time, O(1) space)
The direct solution checks every pair of indices (i, j). For each pair, compare the strings and update the maximum distance when they are different. This requires two nested loops: the outer loop fixes i, and the inner loop scans all j > i. While simple, the algorithm performs n(n-1)/2 comparisons in the worst case. With large arrays, this quickly becomes expensive. This approach still helps verify correctness before optimizing and demonstrates the core observation: only pairs with unequal strings contribute to the answer. The logic relies purely on sequential traversal of the array and string comparisons.
Approach 2: Two-End Scan Using Edge Differences (O(n) time, O(1) space)
The maximum distance between indices is always achieved using one of the array boundaries. If the first and last words differ (words[0] != words[n-1]), the answer is immediately n - 1. If they are equal, a full-span pair cannot be used, so search inward. Scan from the left to find the first index i where words[i] != words[0]. This pair produces distance (n - 1) - i. Then scan from the right to find the first index j where words[j] != words[n - 1]. This pair produces distance j - 0. The result is max(j, n - 1 - i). Only two linear passes are required, and no additional memory is needed.
The key insight: if the outer elements are equal, the optimal pair must include one boundary and the closest element from the opposite side that differs. Any interior pair will always produce a smaller distance. This makes a simple boundary scan sufficient.
Recommended for interviews: The two-end scan approach is the expected solution. It demonstrates that you reason about index distance rather than blindly checking all pairs. Mentioning the brute force method first shows understanding of the baseline, but deriving the O(n) boundary strategy signals strong array reasoning and efficient string comparison logic.
We can observe that at least one of the two words with maximum distance must be at either end of the array (i.e., at index 0 or n - 1). Otherwise, suppose the two words with maximum distance are at indices i and j where 0 < i < j < n - 1. Then words[0] must be the same as words[j], and words[n - 1] must be the same as words[i] (otherwise the distance would be greater). This means words[0] and words[n - 1] are different, and their distance n - 1 - 0 + 1 = n is definitely greater than j - i + 1, which contradicts our assumption. Therefore, at least one of the two words with maximum distance must be at either end of the array.
So, we only need to traverse the array, calculate the distance between each word and the words at both ends of the array, and update the maximum distance.
The time complexity is O(n), where n is the length of array words. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Useful for understanding the problem or when the array size is very small |
| Two-End Boundary Scan | O(n) | O(1) | Optimal solution for all inputs; minimizes comparisons while maximizing index distance |
Maximum Distance Between Unequal Words In Array II • Owen Wu • 70 views views
Practice Maximum Distance Between Unequal Words in Array II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor