You are given a string array words.

Your task is to find the maximum distance between two distinct indices i and j that satisfy the following condition:

• words[i] != words[j] — the words at these two indices must be different.

The distance between indices i and j is defined as j - i + 1, which is essentially the length of the subarray spanning from index i to index j (inclusive).

Return the maximum distance among all such valid pairs. If no valid pair exists (meaning all words in the array are identical), return 0.

Example:

Suppose words = ["a", "b", "a", "a"]:

• The pair (i = 0, j = 1) is valid since "a" != "b", giving a distance of 1 - 0 + 1 = 2.
• The pair (i = 1, j = 3) is valid since "b" != "a", giving a distance of 3 - 1 + 1 = 3.

The maximum distance is 3.

If words = ["a", "a", "a"], every pair of words is identical, so no valid pair exists and the answer is 0.

Key points to keep in mind:

1. The two indices must point to different words — comparing a word with an identical copy of itself does not count.
2. The distance formula j - i + 1 means a pair of adjacent differing words already yields a distance of 2.
3. To maximize the distance, you want the two differing words to be as far apart as possible, ideally near the two ends of the array.

A brute-force approach would check every pair (i, j) and track the maximum j - i + 1, but that takes O(n^2) time. To do better, we need a key observation about where the optimal pair must be located.

Since we want to maximize j - i + 1, we naturally want i to be as small as possible and j to be as large as possible. The extreme case is i = 0 and j = n - 1, giving a distance of n. This leads us to ask: does the optimal pair always involve one of the two endpoints of the array?

The answer is yes, and we can see why through a proof by contradiction:

• Suppose the optimal pair is (i, j) where neither index is an endpoint, i.e., 0 < i and j < n - 1.
• If words[0] != words[j], then the pair (0, j) would be valid and have a larger distance than (i, j) — contradicting that (i, j) is optimal. So it must be that words[0] == words[j].
• Similarly, if words[i] != words[n - 1], the pair (i, n - 1) would be larger. So it must be that words[i] == words[n - 1].
• But now look at the endpoints themselves: words[0] == words[j] and words[n - 1] == words[i], and we know words[i] != words[j]. This forces words[0] != words[n - 1], making (0, n - 1) a valid pair with distance n — strictly larger than j - i + 1. Contradiction again.

Therefore, at least one element of the optimal pair must sit at index 0 or index n - 1.

This insight collapses the problem dramatically: instead of checking all pairs, we only need to compare every word against the first word and the last word:

• If words[i] != words[0], the pair (0, i) gives distance i + 1.
• If words[i] != words[n - 1], the pair (i, n - 1) gives distance n - i.

Taking the maximum over all such candidates yields the answer in a single O(n) pass with O(1) extra space. If no word differs from either endpoint, all words are identical, and the answer naturally stays at 0.

Based on the insight that the optimal pair must include either the first or the last element, we use a single-pass scan that compares every word against the two endpoints of the array.

Step-by-Step Walkthrough

Step 1 — Setup

Record the array length n and initialize the answer:

n = len(words)
ans = 0

Starting ans at 0 handles the edge case where all words are identical — no comparison will ever update it, so 0 is returned as required.

Step 2 — Scan and compare against both endpoints

For each index i from 0 to n - 1, perform two checks:

for i in range(n):
    if words[i] != words[0]:
        ans = max(ans, i + 1)
    if words[i] != words[-1]:
        ans = max(ans, n - i)

• Check against the first word: If words[i] != words[0], then (0, i) is a valid pair. Its distance is i - 0 + 1 = i + 1.
• Check against the last word: If words[i] != words[-1], then (i, n - 1) is a valid pair. Its distance is (n - 1) - i + 1 = n - i.

Each valid candidate updates ans via max.

Step 3 — Return the result

return ans

Why This Covers All Cases

From the proof in the intuition, every optimal pair must anchor at index 0 or index n - 1. The loop exhaustively enumerates:

• All pairs of the form (0, i) — covered by the first check.
• All pairs of the form (i, n - 1) — covered by the second check.

The special pair (0, n - 1) is covered by both checks (when i = n - 1 in the first check, or i = 0 in the second), so no candidate is missed.

Trace Example

Take words = ["a", "b", "a", "a"], so n = 4:

Final answer: 3, matching the pair (1, 3).

Complete Code

class Solution:
    def maxDistance(self, words: List[str]) -> int:
        n = len(words)
        ans = 0
        for i in range(n):
            if words[i] != words[0]:
                ans = max(ans, i + 1)
            if words[i] != words[-1]:
                ans = max(ans, n - i)
        return ans

Complexity Analysis

• Time Complexity: O(n × m), where n is the number of words and m is the average word length — each of the n iterations performs two string comparisons costing up to O(m). If string comparison is treated as O(1), this is simply O(n).
• Space Complexity: O(1) — only the variables n and ans are used; no auxiliary data structures are needed.