LeetCode Problem 3706

Difficulty: 🟡 Medium
Topics: Array, String

Solution

LeetCode 3706 - Maximum Distance Between Unequal Words in Array II

Problem Understanding

We are given an array of strings called words. Our goal is to find two different indices i and j such that the strings at those positions are different, meaning words[i] != words[j].

For every valid pair, the distance is defined as:

$$j - i + 1$$

Unlike the usual definition of distance between indices, this problem counts both endpoints, so adjacent indices have distance 2, and the first and last elements of an array of length n have distance n.

We must return the maximum possible distance among all pairs of indices whose words are different. If every word in the array is identical, then no valid pair exists and the answer is 0.

The input size can be as large as 100,000 elements. This constraint is important because it immediately rules out any solution that checks all pairs of indices. An algorithm with quadratic complexity would perform roughly $10^{10}$ comparisons in the worst case, which is far too slow.

Several edge cases are worth noting:

• The array may contain only one element.
• All words may be identical.
• The optimal pair may not include the first element.
• The optimal pair may not include the last element.
• There may be many repeated values near the ends of the array.
• The maximum distance is inclusive, so the final answer is always one greater than the index difference.

Understanding these cases helps guide us toward an efficient solution.

Approaches

Brute Force

The most direct approach is to examine every pair of indices (i, j) where i < j.

For each pair:

1. Check whether words[i] != words[j].
2. If they are different, compute j - i + 1.
3. Keep track of the largest distance found.

This approach is obviously correct because it explicitly evaluates every valid pair and therefore cannot miss the optimal answer.

However, there are:

$$\frac{n(n-1)}{2}$$

possible pairs.

With n = 100000, this becomes approximately five billion pairs, making the approach completely impractical.

Key Insight

The maximum possible distance always involves one of the array's ends.

Suppose the array length is n.

The largest conceivable distance is obtained by using indices as far apart as possible. Therefore, we should first consider the pair (0, n-1).

If:

words[0] != words[n-1]

then the answer is immediately:

n

because no larger distance can exist.

The only interesting situation occurs when:

words[0] == words[n-1]

Let that common word be x.

Any valid maximum-distance pair must exclude at least one of these endpoints, since using both would violate the inequality requirement.

There are only two possibilities:

• Keep the left endpoint fixed at 0 and find the farthest index from the right whose word differs from x.
• Keep the right endpoint fixed at n-1 and find the farthest index from the left whose word differs from x.

The best answer must be the larger of these two candidates.

This observation allows us to solve the problem with a single scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair of indices
Optimal	O(n)	O(1)	Uses the fact that the maximum distance must involve an endpoint

Algorithm Walkthrough

1. Let n be the length of words.
2. Check whether the first and last words are different.

If words[0] != words[n - 1], then the maximum possible distance already exists between the two ends of the array. Return n. 3. Otherwise, store the common endpoint word:

target = words[0]

4. Scan from the left side toward the right.

Find the first index i such that:

words[i] != target

If found, then using the right endpoint gives distance:

n - i

because:

(n - 1) - i + 1 = n - i

5. Scan from the right side toward the left.

Find the first index j such that:

words[j] != target

If found, then using the left endpoint gives distance:

j + 1

because:

j - 0 + 1 = j + 1

6. Return the larger of the two candidate distances.
7. If no different word is ever found, all words are identical, so return 0.

Why it works

When the first and last words differ, the endpoints already produce the largest possible index separation, so the answer must be n.

When the first and last words are equal to some value x, any valid pair must exclude at least one endpoint. The largest valid distance using the left endpoint comes from the farthest position from the right that differs from x. Similarly, the largest valid distance using the right endpoint comes from the farthest position from the left that differs from x. Every valid maximum-distance pair must belong to one of these two categories, so taking the larger candidate guarantees the optimal answer.

Python Solution

from typing import List

class Solution:
    def maxDistance(self, words: List[str]) -> int:
        n = len(words)

        if words[0] != words[-1]:
            return n

        target = words[0]
        answer = 0

        for i in range(n):
            if words[i] != target:
                answer = max(answer, n - i)
                break

        for j in range(n - 1, -1, -1):
            if words[j] != target:
                answer = max(answer, j + 1)
                break

        return answer

The implementation begins by checking the two endpoints. If they are different, we immediately return n because no larger distance is possible.

If the endpoints contain the same word, we store that word in target. We then perform two linear scans.

The first scan moves from left to right and finds the earliest position whose word differs from target. Pairing that position with the last index yields the largest distance obtainable while keeping the right endpoint fixed.

The second scan moves from right to left and finds the latest position whose word differs from target. Pairing that position with the first index yields the largest distance obtainable while keeping the left endpoint fixed.

The maximum of these two candidate distances is returned.

Go Solution

func maxDistance(words []string) int {
	n := len(words)

	if words[0] != words[n-1] {
		return n
	}

	target := words[0]
	answer := 0

	for i := 0; i < n; i++ {
		if words[i] != target {
			if n-i > answer {
				answer = n - i
			}
			break
		}
	}

	for j := n - 1; j >= 0; j-- {
		if words[j] != target {
			if j+1 > answer {
				answer = j + 1
			}
			break
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. Since the maximum possible answer is at most 100000, there is no risk of integer overflow with Go's int type. The solution uses only a few integer variables and performs two linear scans over the slice.

Worked Examples

Example 1

words = ["leetcode", "leetcode", "codeforces"]

Initial state:

Variable	Value
n	3
words[0]	"leetcode"
words[2]	"codeforces"

Since:

words[0] != words[2]

we immediately return:

n = 3

Answer: 3

Example 2

words = ["a", "b", "c", "a", "a"]

Initial state:

Variable	Value
n	5
words[0]	"a"
words[4]	"a"

Endpoints are equal.

target = "a"
answer = 0

Left-to-right scan:

i	words[i]	Different from target?	Action
0	a	No	Continue
1	b	Yes	answer = max(0, 5 - 1) = 4

Current answer:

answer = 4

Right-to-left scan:

j	words[j]	Different from target?	Action
4	a	No	Continue
3	a	No	Continue
2	c	Yes	answer = max(4, 2 + 1) = 4

Final answer:

4

Example 3

words = ["z", "z", "z"]

Initial state:

Variable	Value
n	3
target	z
answer	0

Left scan:

i	words[i]	Different?
0	z	No
1	z	No
2	z	No

Right scan:

j	words[j]	Different?
2	z	No
1	z	No
0	z	No

No different word is found.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	At most two linear scans of the array
Space	O(1)	Only a few variables are stored

The algorithm performs a constant amount of work per element and never allocates additional data structures proportional to the input size. Therefore the running time is linear and the auxiliary space usage is constant.

Test Cases

from typing import List

s = Solution()

assert s.maxDistance(["leetcode", "leetcode", "codeforces"]) == 3  # example 1
assert s.maxDistance(["a", "b", "c", "a", "a"]) == 4  # example 2
assert s.maxDistance(["z", "z", "z"]) == 0  # example 3

assert s.maxDistance(["a"]) == 0  # single element
assert s.maxDistance(["a", "b"]) == 2  # smallest valid pair
assert s.maxDistance(["a", "a"]) == 0  # two equal words

assert s.maxDistance(["a", "b", "a"]) == 2  # endpoints equal
assert s.maxDistance(["a", "a", "b"]) == 3  # different last word
assert s.maxDistance(["b", "a", "a"]) == 3  # different first word

assert s.maxDistance(["x", "y", "y", "y", "x"]) == 4  # best pair uses left endpoint
assert s.maxDistance(["x", "x", "y", "x", "x"]) == 3  # middle different word

assert s.maxDistance(["a", "b", "c", "d", "e"]) == 5  # all distinct
assert s.maxDistance(["same"] * 100000) == 0  # maximum size, all equal

large = ["a"] * 99999 + ["b"]
assert s.maxDistance(large) == 100000  # maximum distance across array

Test Summary

Test	Why
["leetcode","leetcode","codeforces"]	Provided example with different endpoints
["a","b","c","a","a"]	Provided example with equal endpoints
["z","z","z"]	All words identical
["a"]	Minimum array size
["a","b"]	Smallest valid answer
["a","a"]	Two equal elements
["a","b","a"]	Equal endpoints with one differing middle value
["a","a","b"]	Optimal pair uses last element
["b","a","a"]	Optimal pair uses first element
["x","y","y","y","x"]	Long repeated block in the middle
["x","x","y","x","x"]	Single differing value in center
["a","b","c","d","e"]	All words distinct
["same"] * 100000	Maximum input size, no valid pair
["a"] * 99999 + ["b"]	Maximum possible distance

Edge Cases

Single Element Array

If the array contains only one word, there is no second index available to form a pair. A buggy implementation might accidentally return 1 because of the inclusive distance formula. Our implementation correctly returns 0 because no differing word is ever found during either scan.

All Words Are Identical

Arrays such as:

["z", "z", "z", "z"]

contain no valid pair. This is a common source of mistakes because some solutions assume a differing word will eventually appear. Both scans fail to find a word different from target, leaving answer equal to 0, which is returned.

Equal Endpoints With a Single Different Word

Consider:

["a", "a", "b", "a", "a"]

The endpoints are equal, so the maximum distance cannot use both ends simultaneously. A naive approach might incorrectly return the array length. Our algorithm finds the nearest differing position from each side and computes the best valid distance, producing the correct answer of 3.

Different Endpoints

Consider:

["cat", "cat", "cat", "dog"]

Since the first and last words are already different, the distance between them is the maximum possible distance in the entire array. The algorithm immediately returns n, avoiding any unnecessary scanning while guaranteeing correctness.