LeetCode 3696 - Maximum Distance Between Unequal Words in Array I

LeetCode Problem 3696

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem gives us an array of strings, words, and asks us to find the maximum distance between two indices i and j where the words at those positions are different.

More formally, we want to find two indices such that:

• words[i] != words[j]
• i < j
• the value j - i + 1 is as large as possible

The distance definition is slightly unusual because it counts both endpoints. Instead of the standard difference j - i, the problem defines distance as j - i + 1.

The input is a string array where each element represents a word. The output is a single integer representing the largest valid distance between any two unequal words. If no such pair exists, meaning every word in the array is identical, we return 0.

The constraints are very small:

• 1 <= words.length <= 100
• each word length is at most 10

Since the array size is only 100, even an O(n²) brute-force solution is perfectly acceptable. However, this problem contains an observation that allows an even cleaner O(n) solution.

An important detail is that the distance grows when the chosen indices are farther apart. Therefore, the optimal answer will almost always involve one of the endpoints of the array.

Several edge cases deserve attention:

• If the array contains only one word, there is no second index to compare against, so the answer must be 0.
• If all words are identical, no valid pair exists, so we return 0.
• If only one word differs from the rest, the best answer may involve pairing it with the farthest matching endpoint.
• Since distance includes both endpoints (+1), forgetting this adjustment causes off-by-one errors.

Approaches

Brute Force

The most direct solution is to examine every possible pair (i, j) where i < j.

For each pair, we check whether words[i] != words[j]. If they are different, we compute the distance:

$$j - i + 1$$

We maintain a running maximum and update it whenever we find a larger valid distance.

This approach is correct because it explicitly checks every candidate pair. Since the maximum must belong to one of these pairs, exhaustive search guarantees correctness.

The downside is efficiency. There are O(n²) possible index pairs, so the runtime becomes quadratic. Although n <= 100 makes this perfectly acceptable, we can do better.

Key Insight for an Optimal Solution

The key observation is that the maximum distance must involve one of the array boundaries.

Suppose we want the largest distance between unequal words. Since distance increases as indices become farther apart, the optimal pair should be as spread out as possible.

This means we only need to check:

• whether the first word differs from words near the end
• whether the last word differs from words near the beginning

More specifically:

• Scan from the right to find the farthest index where words[i] != words[0]
• Scan from the left to find the earliest index where words[i] != words[n - 1]

The answer is the maximum of these two possibilities.

Why does this work? Any optimal pair (i, j) has a left endpoint and a right endpoint. If words[i] != words[j], then at least one of the endpoints of the array can replace one side while preserving inequality and potentially increasing distance.

This reduces the time complexity from O(n²) to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair of indices
Optimal	O(n)	O(1)	Uses boundary-word observation

Algorithm Walkthrough

1. Store the array length n.

We need the length repeatedly when computing distances and scanning the array. 2. Initialize max_distance = 0.

This variable stores the largest valid distance found so far. If no unequal pair exists, it remains 0. 3. Scan from right to left while comparing against the first word.

For every index i from n - 1 down to 0, check whether:

words[i] != words[0]

If true, then we can form a valid pair (0, i) with distance:

i + 1

Since we are scanning from the farthest right position, the first match already gives the largest possible distance involving the first word. 4. Scan from left to right while comparing against the last word.

For every index i from 0 to n - 1, check whether:

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

If true, then we can form pair (i, n - 1) with distance:

n - i

Since we scan from the left, the first valid mismatch gives the largest possible distance involving the last word. 5. Return the maximum value found.

If every word is equal, both scans fail to find a mismatch, so the result remains 0.

Why it works

The algorithm relies on the property that maximum distance favors indices that are far apart. For any valid pair (i, j) with unequal words, replacing i with 0 or replacing j with n - 1 cannot reduce the distance if inequality still holds.

Therefore, an optimal solution must involve either the first word or the last word. By checking the farthest mismatch relative to each endpoint, we guarantee that the global maximum distance is found.

Python Solution

from typing import List

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

        # Compare against the first word
        for i in range(n - 1, -1, -1):
            if words[i] != words[0]:
                max_distance = max(max_distance, i + 1)
                break

        # Compare against the last word
        for i in range(n):
            if words[i] != words[-1]:
                max_distance = max(max_distance, n - i)
                break

        return max_distance

The implementation begins by storing the array length in n and initializing max_distance to 0.

The first loop scans from the end of the array toward the beginning. It searches for the farthest word that differs from words[0]. Since we scan from the rightmost side first, the earliest mismatch encountered immediately gives the maximum possible distance involving index 0. After finding such a mismatch, we break because no later index exists.

The second loop performs the symmetric operation. It scans from left to right while comparing against the last word. The first mismatch produces the largest possible distance involving the final index.

Finally, we return the larger of the two candidate distances. If neither loop finds a mismatch, the result remains 0.

Go Solution

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

	// Compare against the first word
	for i := n - 1; i >= 0; i-- {
		if words[i] != words[0] {
			if i+1 > maxDistance {
				maxDistance = i + 1
			}
			break
		}
	}

	// Compare against the last word
	for i := 0; i < n; i++ {
		if words[i] != words[n-1] {
			if n-i > maxDistance {
				maxDistance = n - i
			}
			break
		}
	}

	return maxDistance
}

The Go implementation follows the exact same logic as the Python version.

Go slices already expose their length through len(words), so no special handling is required. Since the constraints are tiny, integer overflow is not a concern. The solution uses only integer variables and direct string comparison, both of which are efficient in Go.

Unlike Python, Go does not provide a built-in max() function for integers, so the implementation updates maxDistance using explicit conditional checks.

Worked Examples

Example 1

Input:

["leetcode", "leetcode", "codeforces"]

The first word is "leetcode".

First Scan (compare with first word)

i	words[i]	Different from "leetcode"?	Distance	max_distance
2	codeforces	Yes	3	3

We stop immediately because scanning starts from the farthest position.

Second Scan (compare with last word)

Last word is "codeforces".

i	words[i]	Different from "codeforces"?	Distance	max_distance
0	leetcode	Yes	3	3

Final answer:

3

Example 2

Input:

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

First Scan (compare with first word "a")

i	words[i]	Different from "a"?	Distance	max_distance
4	a	No	-	0
3	a	No	-	0
2	c	Yes	3	3

Second Scan (compare with last word "a")

i	words[i]	Different from "a"?	Distance	max_distance
0	a	No	-	3
1	b	Yes	4	4

Final answer:

4

Example 3

Input:

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

First Scan

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

Second Scan

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

No valid pair exists.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	At most two full array scans
Space	O(1)	Uses only a few variables

The algorithm performs at most two linear passes through the input array. Each element is visited at most once per scan, giving a total runtime of O(n).

The space complexity is O(1) because the solution only stores a few integer variables regardless of input size. No auxiliary data structures are allocated.

Test Cases

solution = Solution()

# Provided examples
assert solution.maxDistance(
    ["leetcode", "leetcode", "codeforces"]
) == 3  # Example 1

assert solution.maxDistance(
    ["a", "b", "c", "a", "a"]
) == 4  # Example 2

assert solution.maxDistance(
    ["z", "z", "z"]
) == 0  # Example 3

# Single element array
assert solution.maxDistance(
    ["a"]
) == 0  # No pair exists

# Two different words
assert solution.maxDistance(
    ["a", "b"]
) == 2  # Maximum possible distance

# Two identical words
assert solution.maxDistance(
    ["x", "x"]
) == 0  # No unequal pair

# Different word at the end
assert solution.maxDistance(
    ["a", "a", "a", "b"]
) == 4  # Pair first and last

# Different word at the beginning
assert solution.maxDistance(
    ["b", "a", "a", "a"]
) == 4  # Pair first and last

# Alternating values
assert solution.maxDistance(
    ["a", "b", "a", "b", "a"]
) == 5  # Entire range valid

# Interior mismatch only
assert solution.maxDistance(
    ["x", "x", "y", "x"]
) == 3  # Best pair is index 0 and 2

Test	Why
["leetcode","leetcode","codeforces"]	Validates standard mismatch at the end
["a","b","c","a","a"]	Validates best answer from an interior mismatch
["z","z","z"]	Confirms return value 0 when all words match
["a"]	Smallest valid input
["a","b"]	Smallest nonzero answer
["x","x"]	Identical two-element case
["a","a","a","b"]	Tests mismatch only at the far end
["b","a","a","a"]	Symmetric boundary case
["a","b","a","b","a"]	Ensures maximum span is detected
["x","x","y","x"]	Verifies interior mismatch behavior

Edge Cases

All Words Are Equal

An input such as:

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

contains no valid pair because every comparison fails the condition words[i] != words[j]. A naive implementation might accidentally return 1 or another invalid distance if it assumes at least one mismatch exists.

This implementation handles the case correctly because both scans fail to find any unequal word, leaving max_distance unchanged at 0.

Single Element Array

An input like:

["a"]

contains only one index, so no pair can be formed.

Some implementations may accidentally access invalid indices or incorrectly compute a distance. Here, both loops execute safely, find no mismatch, and correctly return 0.

Only One Different Word

Consider:

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

The best pair uses the farthest possible indices, producing distance 4.

A buggy solution might stop after finding the first mismatch without considering maximum span. This implementation avoids that problem by scanning from the boundaries, ensuring the farthest valid mismatch is always chosen.

Off-by-One Distance Errors

The problem defines distance as:

j - i + 1

instead of the usual j - i.

This detail is easy to overlook. For example, indices (0, 2) should produce 3, not 2. The implementation explicitly includes the endpoint contribution by using i + 1 and n - i, which correctly incorporate the +1 term.