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 theshortest distance needed to reach the string target. If the string target does not exist in words, return -1.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6

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

1
2
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

Solution

Method 1 – Direct Distance Calculation

Intuition

For each occurrence of the target in the circular array, compute the minimum distance (either clockwise or counterclockwise) from the start index. Return the smallest such distance, or -1 if the target does not exist.

Approach

  1. Iterate through the array and record all indices where words[i] == target.
  2. For each such index, compute the clockwise and counterclockwise distance from startIndex.
  3. Return the minimum distance found, or -1 if no occurrence.

Code

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

class Solution {
    public int closetTarget(String[] words, String target, int startIndex) {
        int n = words.length, res = n+1;
        for (int i = 0; i < n; ++i) {
            if (words[i].equals(target)) {
                int d = Math.abs(i - startIndex);
                res = Math.min(res, Math.min(d, n - d));
            }
        }
        return res == n+1 ? -1 : res;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def closetTarget(self, words: list[str], target: str, startIndex: int) -> int:
        n = len(words)
        res = n+1
        for i, w in enumerate(words):
            if w == target:
                d = abs(i - startIndex)
                res = min(res, min(d, n - d))
        return -1 if res == n+1 else res

Complexity

  • ⏰ Time complexity: O(n) — One pass through the array.
  • 🧺 Space complexity: O(1) — Only a few variables for tracking minimum distance.