3696. 不同单词间的最大距离 I 🔒

English Version

题目描述

给你一个字符串数组 words。

找到两个 不同 下标 i 和 j 之间的 最大距离 ，且满足以下条件：

• words[i] != words[j]，并且
• 距离定义为 j - i + 1。

返回所有满足条件的下标对中最大的距离。如果不存在有效的下标对，返回 0。

 

示例 1：

示例 2：

示例 3：

 

提示：

• 1 <= words.length <= 100
• 1 <= words[i].length <= 10
• words[i] 由小写英文字母组成。

解法

方法一：一次遍历

我们可以发现，最大距离的两个单词中至少有一个单词在数组的两端（即下标为 $0$或$n - 1$）。否则，假设最大距离的两个单词分别在下标$i$和$j 处，即 \0 < i < j < n - 1$，那么单词$\textit{words}[0]$和$\textit{words}[j]$相同，而单词$\textit{words}[n - 1]$和$\textit{words}[i]$也相同（否则距离会更大），因此单词$\textit{words}[0]$和$\textit{words}[n - 1]$不同，且它们的距离$n - 1 - 0 + 1 = n$一定大于$j - i + 1$，与假设矛盾。因此，最大距离的两个单词中至少有一个单词在数组的两端。

所以，我们只需要遍历数组，计算每个单词与数组两端单词的距离，并更新最大距离。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\textit{words}$ 的长度。空间复杂度 $O(1)$。

Python3

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

Java

class Solution {
    public int maxDistance(String[] words) {
        int n = words.length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (!words[i].equals(words[0])) {
                ans = Math.max(ans, i + 1);
            }
            if (!words[i].equals(words[n - 1])) {
                ans = Math.max(ans, n - i);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxDistance(vector<string>& words) {
        int n = words.size();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (words[i] != words[0]) {
                ans = max(ans, i + 1);
            }
            if (words[i] != words[n - 1]) {
                ans = max(ans, n - i);
            }
        }
        return ans;
    }
};

Go

func maxDistance(words []string) int {
	n := len(words)
	ans := 0
	for i := 0; i < n; i++ {
		if words[i] != words[0] {
			ans = max(ans, i+1)
		}
		if words[i] != words[n-1] {
			ans = max(ans, n-i)
		}
	}
	return ans
}

TypeScript

function maxDistance(words: string[]): number {
    const n = words.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (words[i] !== words[0]) {
            ans = Math.max(ans, i + 1);
        }
        if (words[i] !== words[n - 1]) {
            ans = Math.max(ans, n - i);
        }
    }
    return ans;
}