Maximum Distance Between Unequal Words in Array I

Easy Arrays & Hashing Greedy Original on LeetCode

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 <= 100
  • 1 <= words[i].length <= 10
  • words[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.

00:00
Testcase

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.

ApproachTimeSpace
Brute force (all pairs)O(n² · L)O(1)
Optimal (anchor at the ends)O(n · L)O(1)

1Brute force (all pairs)

TimeO(n² · L)n(n - 1) / 2 pairs, each string comparison costs up to L = 10 characters.
SpaceO(1)Only loop variables.

Check every pair i < j; when the words differ, compare j - i + 1 with the best so far.

  1. best = 0.
  2. For each i < j: if words[i] and words[j] differ, best = max(best, j - i + 1).
  3. 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;
    }
}

2Optimal (anchor at the ends)

TimeO(n · L)At most two linear scans, each step one string comparison of up to L characters.
SpaceO(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.

  1. best = 0.
  2. For j from n - 1 down: the first j with words[j] ≠ words[0] gives best = j + 1; stop.
  3. For i from 0 up: the first i with words[i] ≠ words[n - 1] gives best = max(best, n - i); stop.
  4. 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;
    }
}

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.