You are given a string array words.
Find the maximum distance between two distinct indices i and j such that:
words[i] != words[j], andj - 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 <= 1051 <= words[i].length <= 10words[i] consists of lowercase English letters.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 words[0] must be the same as words[j], and words[n - 1] must be the same as words[i] (otherwise the distance would be greater). This means words[0] and 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 words. The space complexity is O(1).
Java
C++
Go
TypeScript
Practice Maximum Distance Between Unequal Words in Array II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor