Skip to content

3696. Maximum Distance Between Unequal Words in Array I πŸ”’

Description

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.

Solutions

Solution: Single Pass

We can observe that at least one of the two words with maximum distance must be at either end of the array (i.e., at index \(0\) or \(n - 1\)). Otherwise, suppose the two words with maximum distance are at indices \(i\) and \(j\) where \(0 < i < j < n - 1\). Then \(\textit{words}[0]\) must be the same as \(\textit{words}[j]\), and \(\textit{words}[n - 1]\) must be the same as \(\textit{words}[i]\) (otherwise the distance would be greater). This means \(\textit{words}[0]\) and \(\textit{words}[n - 1]\) are different, and their distance \(n - 1 - 0 + 1 = n\) is definitely greater than \(j - i + 1\), which contradicts our assumption. Therefore, at least one of the two words with maximum distance must be at either end of the array.

So, we only need to traverse the array, calculate the distance between each word and the words at both ends of the array, and update the maximum distance.

The time complexity is \(O(n)\), where \(n\) is the length of array \(\textit{words}\). The space complexity is \(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;
}

Comments