Teaching Kids Programming – Minimum Distance of Two Words in a Sentence/String

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the strings text, word0, and word1, return the smallest distance between any two occurrences of word0 and word1 in text, measured in number of words in between. If either word0 or word1 doesn’t appear in text, return -1.

Constraints
word0 and word1 are different.
n ≤ 200,000 where n is the length of text.
Example 1
Input
text = “dog cat hello cat dog dog hello cat world”
word0 = “hello”
word1 = “world”
Output
1
Explanation
There’s only one word “cat” in between the hello and world at the end.

Hints:
store the last of other that you find in the text.

Minimum Distance of Two Words in a Sentence/String

First, we split the string into array of words, then we need to iterate over the words and remember the last index of word1 or word2. At the same time, if the current word (if it is word1 or word2) but different than the last word seen, we calculate the distance.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def solve(self, s, w1, w2):
        arr = s.split()
        n = len(arr)
        last = None
        ans = math.inf
        for i, cur in enumerate(arr):
            if cur in (w1, w2):
                if last != None and arr[last] != cur:
                    ans = min(ans, i - last - 1)
                last = i
        return ans if ans != math.inf else -1

class Solution:
    def solve(self, s, w1, w2):
        arr = s.split()
        n = len(arr)
        last = None
        ans = math.inf
        for i, cur in enumerate(arr):
            if cur in (w1, w2):
                if last != None and arr[last] != cur:
                    ans = min(ans, i - last - 1)
                last = i
        return ans if ans != math.inf else -1

The time complexity is O(N), and the space complexity is also O(N). The distance is calculate the number of words between, and thus the index difference needs to decremented by one.

–EOF (The Ultimate Computing & Technology Blog) —