You are given a string s of length n made up of lowercase English letters.

Your task is to find and return the smallest index i such that the character at position i is equal to the character at the mirrored position from the end, that is s[i] == s[n - i - 1].

In other words, you compare each character with its counterpart from the opposite end of the string:

• The character at index 0 is compared with the character at index n - 1.
• The character at index 1 is compared with the character at index n - 2.
• And so on, moving inward from both ends.

The moment you find an index i where these two characters match, you return that index. Since you start checking from the beginning of the string, the first match you encounter is guaranteed to be the smallest such index.

If you go through all the positions and never find a matching pair, return -1.

The problem asks for the smallest index i where s[i] matches its mirrored character s[n - i - 1]. The key observation is that since we want the smallest index, we should naturally start checking from the very beginning of the string and move forward. The first match we find will automatically be the smallest valid index.

Another important detail is that each index i is paired with its mirror n - i - 1. As i grows from 0 toward the middle, its mirror shrinks from n - 1 toward the middle. Once i passes the midpoint, the pairs simply repeat what we have already checked (just swapped). For example, the pair (i, n - i - 1) is the same pair as (n - i - 1, i). This means we only need to examine the first half of the string to cover every unique pair.

So the natural approach is to walk through indices from 0 up to the middle of the string, comparing each character with its mirror. The moment we find s[i] == s[n - i - 1], we return i immediately, knowing it is the smallest possible answer. If we finish scanning the first half without finding any match, then no such index exists, and we return -1.

Pattern Learn more about Two Pointers patterns.

Solution 1: Simulation

We directly simulate the comparison process described in the problem.

The implementation steps are as follows:

1. Iterate over the first half of the string. We loop i from 0 up to len(s) // 2 + 1. We only need to scan the first half because each index i and its mirror n - i - 1 form a unique pair, and pairs in the second half merely repeat those in the first half.

2. Compare each character with its mirror. For each index i, we check whether s[i] == s[-i - 1]. Here, the negative index -i - 1 is a convenient way in Python to reference the mirrored position n - i - 1, counting backward from the end of the string.

3. Return the first match. Since we scan from the beginning, the first index i that satisfies s[i] == s[-i - 1] is guaranteed to be the smallest valid index. We return it immediately.

4. Handle the no-match case. If the loop completes without finding any matching pair, we return -1.

The reference code expresses this cleanly:

class Solution:
    def firstMatchingIndex(self, s: str) -> int:
        for i in range(len(s) // 2 + 1):
            if s[i] == s[-i - 1]:
                return i
        return -1

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the string s. In the worst case, we scan up to half of the string, which is still linear in n.
• Space Complexity: O(1), since we only use a constant amount of extra space for the loop variable, regardless of the input size.