Maximum Distance Between Unequal Words in Array I
Maximum Distance Between Unequal Words in Array I is a easy arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (anchor at the ends), runs in O(n · L) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (all pairs) up.
Problem
You are given an array of strings words. For two indices i < j with words[i] != words[j], their distance is j - i + 1.
Return the largest distance over all such pairs. If every word in the array is the same (so no pair qualifies), return 0.
Examples
Example 1
- Input
words = ["go", "go", "to", "go"]- Output
3- Why
- Indices 0 and 2 hold different words, giving 2 - 0 + 1 = 3. No unequal pair is farther apart.
Example 2
- Input
words = ["ab", "cd", "ab", "ab", "ef"]- Output
5- Why
- The first and last words already differ, so the whole array counts: 4 - 0 + 1 = 5.
Example 3
- Input
words = ["x", "x"]- Output
0- Why
- Every word is the same, so there is no valid pair.
Constraints
1 <= words.length <= 1001 <= words[i].length <= 10words[i]contains only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (all pairs) | O(n² · L) | O(1) |
| Optimal (anchor at the ends) | O(n · L) | O(1) |
1Brute force (all pairs)
O(n² · L)n(n - 1) / 2 pairs, each string comparison costs up to L = 10 characters.O(1)Only loop variables.Check every pair i < j; when the words differ, compare j - i + 1 with the best so far.
- best = 0.
- For each i < j: if words[i] and words[j] differ, best = max(best, j - i + 1).
- Return best.
class Solution {
public int maxDistance(String[] words) {
int n = words.length, best = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (!words[i].equals(words[j])) {
best = Math.max(best, j - i + 1);
}
}
}
return best;
}
}class Solution:
def maxDistance(self, words: List[str]) -> int:
n = len(words)
best = 0
for i in range(n):
for j in range(i + 1, n):
if words[i] != words[j]:
best = max(best, j - i + 1)
return bestclass Solution {
public:
int maxDistance(vector<string>& words) {
int n = words.size(), best = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (words[i] != words[j]) {
best = max(best, j - i + 1);
}
}
}
return best;
}
};function maxDistance(words) {
const n = words.length;
let best = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (words[i] !== words[j]) {
best = Math.max(best, j - i + 1);
}
}
}
return best;
}2Optimal (anchor at the ends)
O(n · L)At most two linear scans, each step one string comparison of up to L characters.O(1)Only indices.Some best pair always touches an end. Take any valid pair (i, j). If words[0] ≠ words[j], then (0, j) is at least as long. If words[n - 1] ≠ words[i], then (i, n - 1) is at least as long. Otherwise words[0] = words[j] and words[n - 1] = words[i], and since words[i] ≠ words[j] the pair (0, n - 1) is valid and longest of all. So pair index 0 with the farthest word that differs from it, pair the last index with the farthest word on the left that differs from it, and take the larger.
- best = 0.
- For j from n - 1 down: the first j with words[j] ≠ words[0] gives best = j + 1; stop.
- For i from 0 up: the first i with words[i] ≠ words[n - 1] gives best = max(best, n - i); stop.
- Return best.
class Solution {
public int maxDistance(String[] words) {
int n = words.length, best = 0;
for (int j = n - 1; j > 0; j--) {
if (!words[j].equals(words[0])) {
best = j + 1;
break;
}
}
for (int i = 0; i < n - 1; i++) {
if (!words[i].equals(words[n - 1])) {
best = Math.max(best, n - i);
break;
}
}
return best;
}
}class Solution:
def maxDistance(self, words: List[str]) -> int:
n = len(words)
best = 0
for j in range(n - 1, 0, -1):
if words[j] != words[0]:
best = j + 1
break
for i in range(n - 1):
if words[i] != words[n - 1]:
best = max(best, n - i)
break
return bestclass Solution {
public:
int maxDistance(vector<string>& words) {
int n = words.size(), best = 0;
for (int j = n - 1; j > 0; j--) {
if (words[j] != words[0]) {
best = j + 1;
break;
}
}
for (int i = 0; i < n - 1; i++) {
if (words[i] != words[n - 1]) {
best = max(best, n - i);
break;
}
}
return best;
}
};function maxDistance(words) {
const n = words.length;
let best = 0;
for (let j = n - 1; j > 0; j--) {
if (words[j] !== words[0]) {
best = j + 1;
break;
}
}
for (let i = 0; i < n - 1; i++) {
if (words[i] !== words[n - 1]) {
best = Math.max(best, n - i);
break;
}
}
return best;
}Edge cases to test
- A single word: the answer is 0
- All words equal: the answer is 0
- First and last words differ: the answer is the array length
- The only different word sits in the middle
Hints
Hint 1
Checking every pair works for 100 words.
Hint 2
If the best pair does not use index 0, then words[0] equals its left word. What does that tell you about pairing index 0 with its right word instead?
Hint 3
A best pair can always use the first or the last index. Scan from each end.
FAQ
What is the best time complexity for Maximum Distance Between Unequal Words in Array I?
Optimal (anchor at the ends) runs in O(n · L) time and O(1) extra space. At most two linear scans, each step one string comparison of up to L characters.
Which pattern does Maximum Distance Between Unequal Words in Array I use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Maximum Distance Between Unequal Words in Array I?
Yes. Brute force (all pairs) takes O(n² · L) time and O(1) space. Check every pair i < j; when the words differ, compare j - i + 1 with the best so far.
Which edge cases should I test for Maximum Distance Between Unequal Words in Array I?
A single word: the answer is 0; All words equal: the answer is 0; First and last words differ: the answer is the array length; The only different word sits in the middle.