Shortest Word Distance III - Practice Coding Problems

Shortest Word Distance III - Problem

Array String Easy

Given an array of strings wordsDict and two strings word1 and word2 that already exist in the array, return the shortest distance between any two occurrences of these words in the list.

Note: word1 and word2 may be the same. It is guaranteed that they represent two individual words in the list.

The distance between two words is the absolute difference between their indices.

Input & Output

Example 1 — Same Words

$ Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"

› Output: 3

💡 Note: "makes" appears at indices 1 and 4. The distance between them is |4 - 1| = 3.

Example 2 — Different Words

$ Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"

› Output: 1

💡 Note: "makes" appears at indices 1 and 4, "coding" appears at index 3. The shortest distance is between indices 3 and 4: |4 - 3| = 1.

Example 3 — Adjacent Words

$ Input: wordsDict = ["a", "b", "c"], word1 = "a", word2 = "b"

› Output: 1

💡 Note: "a" is at index 0, "b" is at index 1. Distance is |1 - 0| = 1.

Constraints

1 ≤ wordsDict.length ≤ 3 × 10⁴
1 ≤ wordsDict[i].length ≤ 10
wordsDict[i] consists of lowercase English letters
word1 and word2 are in wordsDict
word1 and word2 may be the same

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and two target words (possibly same)

Process

Track positions and calculate distances efficiently

Output

Return minimum distance between any two occurrences

Key Takeaway

🎯 Key Insight: When both target words are identical, we must find the minimum distance between different occurrences, not the same position

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is handling the special case where both words are identical - we need to find the minimum distance between different occurrences of the same word. Best approach uses single pass tracking to achieve O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(n)	Find all positions of both words, then check every possible pair
Single Pass Optimization	O(n)	O(1)	Track latest positions while scanning array once to find minimum distance

Brute Force - Check All Pairs — Algorithm Steps

Find all indices of word1
Find all indices of word2
Compare every pair to find minimum distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Positions

Collect all indices where each word appears

Compare Pairs

Check distance between every pair of positions

Return Minimum

Keep track of smallest distance found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char words[][100], int n, char* word1, char* word2) {
    int positions1[1000], positions2[1000];
    int count1 = 0, count2 = 0;
    
    // Find all positions of word1 and word2
    for (int i = 0; i < n; i++) {
        if (strcmp(words[i], word1) == 0) {
            positions1[count1++] = i;
        }
        if (strcmp(words[i], word2) == 0) {
            positions2[count2++] = i;
        }
    }
    
    int minDistance = INT_MAX;
    
    // If same word, compare different positions
    if (strcmp(word1, word2) == 0) {
        for (int i = 0; i < count1; i++) {
            for (int j = i + 1; j < count1; j++) {
                int dist = abs(positions1[i] - positions1[j]);
                if (dist < minDistance) {
                    minDistance = dist;
                }
            }
        }
    } else {
        // Different words, compare all pairs
        for (int i = 0; i < count1; i++) {
            for (int j = 0; j < count2; j++) {
                int dist = abs(positions1[i] - positions2[j]);
                if (dist < minDistance) {
                    minDistance = dist;
                }
            }
        }
    }
    
    return minDistance;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char words[1000][100];
    int n = 0;
    
    // Parse array manually
    char* token = strtok(line, "[]\",");
    while (token != NULL) {
        while (*token == ' ') token++; // Skip spaces
        if (strlen(token) > 0) {
            strcpy(words[n++], token);
        }
        token = strtok(NULL, "[]\",");
    }
    
    char word1[100], word2[100];
    fgets(word1, sizeof(word1), stdin);
    fgets(word2, sizeof(word2), stdin);
    
    word1[strcspn(word1, "\n")] = 0;
    word2[strcspn(word2, "\n")] = 0;
    
    int result = solution(words, n, word1, word2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Finding positions is O(n), but comparing all pairs can be O(n²) if all words match

⚠ Quadratic Growth

Space Complexity

O(n)

Store all positions of both words in arrays

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler