跳转至

3696. Maximum Distance Between Unequal Words in Array I 🔒

题目描述

You are given a string array words.

Find the maximum distance between two distinct indices i and j such that:

  • words[i] != words[j], and
  • the distance is defined as j - i + 1.

Return the maximum distance among all such pairs. If no valid pair exists, return 0.

 

Example 1:

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

Output: 3

Explanation:

In this example, words[0] and words[2] are not equal, and they have the maximum distance 2 - 0 + 1 = 3.

Example 2:

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

Output: 4

Explanation:

In this example words[1] and words[4] have the largest distance of 4 - 1 + 1 = 4.

Example 3:

Input: words = ["z","z","z"]

Output: 0

Explanation:

In this example all the words are equal, thus the answer is 0.

 

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.

解法

方法一：一次遍历

我们可以发现，最大距离的两个单词中至少有一个单词在数组的两端（即下标为 \(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)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
}

评论