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 conditions:

• words[i] != words[j] — the words at the two indices must be different, and
• the distance between them is defined as j - i + 1.

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

Key points to understand:

1. The distance is not simply j - i; it is j - i + 1, which counts the number of elements in the range from index i to index j (inclusive).
2. The two indices must hold different words. Pairs where words[i] == words[j] do not count.
3. To maximize j - i + 1, we want i to be as small as possible and j to be as large as possible, while still keeping words[i] and words[j] different.

Example:

• If words = ["a", "b", "c", "a"], the pair (i = 0, j = 2) gives words[0] = "a" and words[2] = "c", which are different, so the distance is 2 - 0 + 1 = 3. The pair (i = 1, j = 3) also gives a distance of 3. The pair (i = 0, j = 3) is invalid because both words are "a". Hence the answer is 3.
• If words = ["x", "x", "x"], every pair has equal words, so no valid pair exists, and the answer is 0.

A brute-force approach would check every pair (i, j) and take the maximum distance among pairs with different words, costing O(n^2) time. But a key observation lets us do much better.

To maximize j - i + 1, we want i to be small and j to be large. The most extreme candidates are the two ends of the array: index 0 and index n - 1.

Claim: in any optimal pair, at least one of the two indices must be an endpoint of the array (0 or n - 1).

Why? Suppose the best pair (i, j) has neither index at an endpoint, i.e., 0 < i and j < n - 1. Then:

• words[0] must equal words[j] — otherwise the pair (0, j) would be valid and longer, contradicting optimality.
• words[n - 1] must equal words[i] — otherwise the pair (i, n - 1) would be valid and longer.

But since words[i] != words[j], combining the two equalities gives words[n - 1] != words[0]. That makes (0, n - 1) itself a valid pair with distance n, the largest possible — again contradicting the assumption that (i, j) was optimal.

So the assumption fails, and every optimal answer involves words[0] or words[n - 1].

This immediately suggests a single-pass strategy: for each index i, only two pairings matter —

• pair i with the first word: if words[i] != words[0], the distance is i - 0 + 1 = i + 1;
• pair i with the last word: if words[i] != words[n - 1], the distance is (n - 1) - i + 1 = n - i.

Taking the maximum over all such candidates covers every possible optimal pair, reducing the problem to a simple O(n) scan with O(1) extra space.

Based on the observation that at least one index of the optimal pair must be an endpoint, the implementation becomes a single pass over the array, comparing every word against the first word and the last word.

Step-by-Step Walkthrough

Step 1: Initialization

n = len(words)
ans = 0

• n is the length of the array.
• ans holds the best distance found so far. Starting it at 0 automatically handles the "no valid pair exists" case — if every comparison fails, ans is never updated and 0 is returned.

Step 2: Single pass — compare each word with both endpoints

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)

For each index i, two candidate pairs are evaluated:

1. Pair (0, i) — if words[i] != words[0], this is a valid pair, and its distance is i - 0 + 1 = i + 1.
2. Pair (i, n - 1) — if words[i] != words[-1] (i.e., words[n - 1]), this is a valid pair, and its distance is (n - 1) - i + 1 = n - i.

Each valid candidate is folded into ans via max.

Two boundary details worth noting:

• When i = 0, the first condition words[0] != words[0] is always false, so the invalid "pair" of an index with itself is never counted. The same holds for i = n - 1 in the second condition.
• If words[0] != words[n - 1], the loop naturally captures the maximum possible answer n — for example, at i = n - 1 the first check yields (n - 1) + 1 = n.

Step 3: Return the result

return ans

Why This Covers All Cases

The proof from the intuition guarantees that any optimal pair (i, j) has i = 0 or j = n - 1:

• If i = 0, the pair is found by the first if when the loop reaches index j.
• If j = n - 1, the pair is found by the second if when the loop reaches index i.

So no optimal answer can be missed by this scan.

Data Structures and Patterns

• No auxiliary data structures are needed — just two scalar variables.
• The pattern is a greedy / endpoint-anchoring technique: instead of enumerating all O(n^2) pairs, a structural property of the optimum shrinks the candidate set to O(n) pairs anchored at the array's two ends.

Complexity Analysis

• Time complexity: O(n) — a single traversal of the array, with each iteration doing constant work (two string comparisons; if string lengths are bounded by a constant, each comparison is O(1)).
• Space complexity: O(1) — only n and ans are stored, independent of input size.

Alternative Perspective: Two-Pointer Variant

The same endpoint insight admits another O(n) formulation. Find the largest j with words[j] != words[0] and the smallest i with words[i] != words[n - 1]; the answer is max(j + 1, n - i) (or 0 if neither exists). This computes identical results, since both methods exhaust exactly the pairs anchored at an endpoint — the single-pass version above simply merges both searches into one loop.