Maximum Distance Between Unequal Words in Array I - Solution & Explanation
Problem Statement
You are given a string array words.
Find the maximum distance between two distinct indices i and j such that:
words[i] != words[j], and- the distance is defined as
j - 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 <= 1001 <= words[i].length <= 10words[i]consists of lowercase English letters.
Approach Overview
Problem Overview: You get an array of words. The task is to find the maximum distance between two indices i and j such that words[i] != words[j]. Distance is measured as |i - j|, so you want the farthest pair of positions that contain different words.
Approach 1: Brute Force Pair Check (O(n^2) time, O(1) space)
Check every possible pair of indices using two nested loops. For each pair (i, j), compare words[i] and words[j]. If they are different, compute j - i and update the maximum distance. This guarantees the correct answer because every pair is examined. The downside is the quadratic time complexity, which becomes slow as the array grows.
This approach mainly demonstrates the core observation: the answer depends only on pairs of unequal strings. It works for small inputs but is rarely the expected solution in interviews involving array traversal.
Approach 2: Edge Comparison with Linear Scan (O(n) time, O(1) space)
The maximum possible distance in an array of length n is n - 1, which occurs between the first and last elements. Start by checking words[0] and words[n-1]. If they are different, the answer is immediately n - 1.
If the first and last words are the same, the optimal pair must involve one of the ends and a different word somewhere inside the array. Scan from the left to find the first index i where words[i] != words[0]. That pair gives distance n - 1 - i. Then scan from the right to find the first index j where words[j] != words[0]. That pair gives distance j. The result is max(n - 1 - i, j).
This works because if both ends contain the same string, any valid maximum-distance pair must replace one of those ends with the farthest different word. The algorithm performs only a single pass over the string array and uses constant extra space, making it optimal for this problem.
Recommended for interviews: Start by explaining the brute force pair comparison to show you understand the requirement. Then move to the linear scan strategy. Interviewers expect the O(n) observation that the maximum distance must involve one of the array edges, which reduces the search to a single pass.
Solution
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).
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n^2) | O(1) | Useful for understanding the problem or very small arrays |
| Edge Comparison with Linear Scan | O(n) | O(1) | Optimal solution for general cases and expected in interviews |
Video Solution
leetcode 3696 Linear Scan for problem solving - Maximum Distance Between Unequal Words in Array I • Code-Yao • 54 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Maximum Distance Between Unequal Words in Array I easy or hard?
Maximum Distance Between Unequal Words in Array I Python/Java solution
How to solve Maximum Distance Between Unequal Words in Array I in O(n)?
What is the best approach for Maximum Distance Between Unequal Words in Array I?
Is Maximum Distance Between Unequal Words in Array I asked at Google/Amazon/Meta?
What data structure is used in Maximum Distance Between Unequal Words in Array I?
What is the time complexity of Maximum Distance Between Unequal Words in Array I?
Ready to solve this problem?
Practice Maximum Distance Between Unequal Words in Array I with our built-in code editor and test cases.
Practice on FleetCode