Maximum Distance Between Unequal Words in Array I - Video Solutions
leetcode 3696 Linear Scan for problem solving - Maximum Distance Between Unequal Words in Array I
Maximum Distance Between Unequal Words in Array I - Video Solution
Watch 2 video solutions for Maximum Distance Between Unequal Words in Array I, a easy level problem involving Array, String. This walkthrough by Code-Yao has 54 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |