# Shortest Distance to Target String in a Circular Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/shortest-distance-to-target-string-in-a-circular-array)
Canonical: https://scaleengineer.com/dsa/problems/shortest-distance-to-target-string-in-a-circular-array
**Data structures:** Array, String
---
## Problem
You are given a **0-indexed** **circular** string array `words` and a string `target`. A **circular array** means that the array's end connects to the array's beginning.

* Formally, the next element of `words[i]` is `words[(i + 1) % n]` and the previous element of `words[i]` is `words[(i - 1 + n) % n]`, where `n` is the length of `words`.

Starting from `startIndex`, you can move to either the next word or the previous word with `1` step at a time.

Return _the **shortest** distance needed to reach the string_ `target`. If the string `target` does not exist in `words`, return `-1`.

**Example 1:**

**Input:** words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
**Output:** 1
**Explanation:** 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
**Explanation:** 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
**Explanation:** 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`

# Approaches
## Single Pass Iteration
This approach involves a straightforward linear scan of the entire `words` array. For every element that matches the `target` string, we calculate its shortest circular distance from the `startIndex`. We maintain a variable to keep track of the minimum distance found so far across all matches.
**Time:** O(N * L), where `N` is the length of the `words` array and `L` is the maximum length of a string in the array. We iterate through all `N` words, and for each word, the string comparison `equals()` takes O(L) time in the worst case. · **Space:** O(1), as we only use a constant amount of extra space for variables like `minDist` and the loop counter.
**Pros:** The logic is simple to understand and implement.; It correctly finds the shortest distance by exhaustively checking all possibilities.
**Cons:** This approach is less efficient as it always iterates through the entire array, regardless of how close the target is to the `startIndex`.
### Explanation
The core idea is to find all occurrences of the `target` string and then determine which one is closest to the `startIndex`. We can achieve this with a single pass through the array.

We initialize a variable, `minDist`, to the maximum possible integer value to act as a placeholder for the minimum distance. Then, we loop through each word in the `words` array from index 0 to `n-1`.

For each word, we check if it matches the `target`. If it does, we calculate the shortest distance from `startIndex` to the current index `i`. In a circular array of length `n`, the distance between two indices `a` and `b` is the minimum of the clockwise distance `abs(a - b)` and the counter-clockwise distance `n - abs(a - b)`. We update `minDist` with this value if it's smaller than the current `minDist`.

After checking all the words, if `minDist` is still at its initial maximum value, it implies the `target` was never found, and we should return -1. Otherwise, `minDist` holds the shortest distance to a target string, which we return.

```java
class Solution {
    public int closetTarget(String[] words, String target, int startIndex) {
        int n = words.length;
        int minDist = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            if (words[i].equals(target)) {
                int dist = Math.abs(i - startIndex);
                int circularDist = Math.min(dist, n - dist);
                minDist = Math.min(minDist, circularDist);
            }
        }

        return (minDist == Integer.MAX_VALUE) ? -1 : minDist;
    }
}
```
### Algorithm
- Initialize a variable `minDist` to a very large number (e.g., `Integer.MAX_VALUE`).
- Iterate through the `words` array with an index `i` from `0` to `n-1`, where `n` is the length of the array.
- Inside the loop, if `words[i]` equals the `target` string:
    - Calculate the direct distance: `dist = abs(i - startIndex)`.
    - Calculate the circular distance: `circularDist = n - dist`.
    - The shortest distance to this occurrence is `min(dist, circularDist)`.
    - Update `minDist` by taking the minimum of its current value and this new shortest distance.
- After the loop, if `minDist` remains at its initial large value, the target was not found, so return -1. Otherwise, return `minDist`.

## Bidirectional Search
A more optimized approach is to perform a bidirectional search starting from the `startIndex`. Instead of scanning the entire array, we expand our search outwards from the starting point, one step at a time in both the left and right directions. The first time we encounter the `target` string, we are guaranteed to have found it via the shortest possible path.
**Time:** O(N * L) in the worst case, where `N` is the number of words and `L` is the maximum string length. The worst case occurs when the target is not found or is located at the maximum possible distance (`n/2`), requiring us to check all `n` elements. However, its average-case performance is better than the single-pass approach. · **Space:** O(1), as it uses only a few variables to keep track of indices and distance, requiring constant extra space.
**Pros:** More efficient on average, as it can terminate early.; If the target is at or near the `startIndex`, the solution is found very quickly.; The logic directly models the problem of finding the 'closest' item.
**Cons:** The worst-case time complexity is the same as the brute-force approach, although it performs better on average.
### Explanation
This method simulates the process of moving away from `startIndex` one step at a time, simultaneously to the right and to the left. We use a loop that iterates through possible distances, from 0 upwards.

The maximum possible shortest distance in a circular array of size `n` is `n / 2`. Therefore, we only need to check distances from `0` to `n / 2`.

For each distance `d`, we calculate the corresponding indices: `(startIndex + d) % n` for the rightward move and `(startIndex - d + n) % n` for the leftward move. The `+ n` in the leftward calculation handles potential negative results from the subtraction, ensuring the index remains valid.

We check if the word at either of these two indices matches the `target`. If a match is found, we can immediately return the current distance `d`, as our incremental search guarantees this is the shortest path. If the loop finishes without finding any match, it means the `target` is not present in the array, and we return -1.

```java
class Solution {
    public int closetTarget(String[] words, String target, int startIndex) {
        int n = words.length;
        for (int dist = 0; dist <= n / 2; dist++) {
            // Check `dist` steps to the right
            int rightIndex = (startIndex + dist) % n;
            if (words[rightIndex].equals(target)) {
                return dist;
            }
            
            // Check `dist` steps to the left
            int leftIndex = (startIndex - dist + n) % n;
            if (words[leftIndex].equals(target)) {
                return dist;
            }
        }
        
        return -1;
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- Loop with a `distance` variable `d` from `0` up to `n / 2`.
- In each iteration, check two positions: `d` steps to the right and `d` steps to the left of `startIndex`.
- Calculate the right index: `rightIdx = (startIndex + d) % n`.
- If `words[rightIdx]` matches the `target`, return `d` because this is the shortest distance.
- Calculate the left index: `leftIdx = (startIndex - d + n) % n`.
- If `words[leftIdx]` matches the `target`, return `d`.
- If the loop completes without finding the target, it means the target is not in the array, so return -1.

# Solutions
### Java

```java
class Solution {
public
  int closetTarget(String[] words, String target, int startIndex) {
    int n = words.length;
    int ans = n;
    for (int i = 0; i < n; ++i) {
      String w = words[i];
      if (w.equals(target)) {
        int t = Math.abs(i - startIndex);
        ans = Math.min(ans, Math.min(t, n - t));
      }
    }
    return ans == n ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int closetTarget(vector<string> &words, string target, int startIndex) {
    int n = words.size();
    int ans = n;
    for (int i = 0; i < n; ++i) {
      auto w = words[i];
      if (w == target) {
        int t = abs(i - startIndex);
        ans = min(ans, min(t, n - t));
      }
    }
    return ans == n ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def closetTarget(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

```