Watch the video solution for Maximum Distance Between Unequal Words in Array II, a medium level problem involving Array, String. This walkthrough by Owen Wu has 70 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |