#2515

Easy

LeetCode Problem Workspace

Shortest Distance to Target String in a Circular Array

Find the shortest distance to a target string in a circular array with either left or right movement options.

Problem Statement

You are given a circular array of strings called words and a string target. The array is circular, meaning the end connects back to the beginning. Starting from a given index, you can either move to the next element or to the previous one with 1 step at a time.

Your task is to return the shortest distance to the target string. If the target string doesn't exist in the array, return -1. The solution should handle cases where the array and string have varying lengths, with edge cases like the target being absent.

Examples

Example 1

Input: words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1

Output: 1

We start from index 1 and can reach "hello" by

moving 3 units to the right to reach index 4.
moving 2 units to the left to reach index 4.
moving 4 units to the right to reach index 0.
moving 1 unit to the left to reach index 0. The shortest distance to reach "hello" is 1.

Example 2

Input: words = ["a","b","leetcode"], target = "leetcode", startIndex = 0

Output: 1

We start from index 0 and can reach "leetcode" by

moving 2 units to the right to reach index 3.
moving 1 unit to the left to reach index 3. The shortest distance to reach "leetcode" is 1.

Example 3

Input: words = ["i","eat","leetcode"], target = "ate", startIndex = 0

Output: -1

Since "ate" does not exist in words, we return -1.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] and target consist of only lowercase English letters.
0 <= startIndex < words.length

Solution Approach

Calculate Distances in Both Directions

First, calculate the distance moving right, and then calculate the distance moving left. Both directions need to be considered because of the circular nature of the array. Use modulo operations to wrap around when necessary.

Compare Distances to Find the Shortest Path

After calculating both left and right distances, compare them and return the smaller value. This ensures you choose the shortest path regardless of the direction, handling both cases where the target is closer from the right or left.

Handle Edge Case of Missing Target

If the target string doesn't exist in the array, return -1 immediately. This check must be performed before any distance calculations to ensure efficient processing.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used to traverse the array. In the worst case, you may need to check all elements in the array, making the time complexity O(n), where n is the length of the array. The space complexity is O(1) as no additional data structures are required, just simple calculations.

What Interviewers Usually Probe

Evaluating the candidate’s understanding of array traversal with circular properties.
Looking for the ability to handle multiple path options and compare results efficiently.
Testing edge case handling where the target string may not exist in the array.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the circular nature of the array when calculating distances.
Overcomplicating the solution by unnecessarily checking for all possible paths, rather than focusing on the two directions.
Not handling the edge case where the target does not exist in the array, which could lead to incorrect results.

Follow-up variants

A variant could involve considering distances in a non-circular array, simplifying the problem by eliminating the need to wrap around.
You could extend the problem by introducing multiple targets and needing to find the shortest distance to any one of them.
A more complex variant would involve adding constraints, such as having to pass through certain words before reaching the target.

FAQ

What is the best approach to solve the "Shortest Distance to Target String in a Circular Array" problem?

The best approach is to calculate the distances in both directions (left and right) and then choose the smaller one. Don't forget to handle the case where the target is not in the array.

How do I handle the circular nature of the array?

You can handle the circular nature by using modulo operations when calculating the distances, ensuring you correctly wrap around the array.

What if the target string doesn't exist in the array?

If the target string doesn't exist in the array, return -1 as per the problem's constraints.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of words in the array. You may need to check all words to find the target.

Can this problem be solved with a more efficient algorithm?

This problem is generally solved with a linear scan, but optimization could focus on early termination when the target is found or when distance calculations can be skipped.

terminal

Solution

Solution 1: Single Traversal

We traverse the array $\textit{words}$$,$ find the words equal to $\textit{target}$, and compute their distance $t$ from $\textit{startIndex}$. The shortest distance in this case is $\min(t, n - t)$, so we only need to keep updating the minimum value.

1

2

3

4

5

6

7

8

9

class Solution:
    def closestTarget(self, words: List[str], target: str, startIndex: int) -> int:
        n = len(words)
        ans = n
        for i, w in enumerate(words):
            if w == target:
                t = abs(i - startIndex)
                ans = min(ans, t, n - t)
        return -1 if ans == n else ans

Continue Practicing

#2512 reward top k students #2506 count pairs of similar strings #2496 maximum value of a string in an array