LeetCode Problem 3884

Difficulty: 🟢 Easy
Topics: Two Pointers, String

Solution

LeetCode 3884 - First Matching Character From Both Ends

Problem Understanding

This problem gives us a string s of length n consisting of lowercase English letters.

For every index i, we compare two characters:

• The character at position i, which is s[i]
• The character at the mirrored position from the other end, which is s[n - i - 1]

We must find the smallest index i where these two characters are equal.

If such an index exists, we return it immediately. If no index satisfies the condition, we return -1.

The important detail is that we are comparing symmetric positions from the beginning and end of the string. For example, in a string of length 7:

Index i	Mirrored Index n - i - 1
0	6
1	5
2	4
3	3
4	2
5	1
6	0

Notice that when the string length is odd, the middle character compares with itself. Since a character is always equal to itself, every odd-length string will have at least one valid index at the center position.

The constraints are very small:

• 1 <= s.length <= 100
• Only lowercase English letters appear

Because the input size is tiny, efficiency is not a concern. However, we can still design a clean optimal solution.

Important edge cases include:

• A string of length 1, where the only character compares with itself.
• Odd-length strings where only the center position matches.
• Strings where no mirrored pair matches.
• Strings where the very first pair already matches.
• Even-length strings that may or may not contain a matching mirrored pair.

Approaches

Brute Force Approach

The most direct approach is to check every possible index i.

For each index:

1. Compute its mirrored index n - i - 1.
2. Compare s[i] and s[n - i - 1].
3. If they are equal, immediately return i.

If we finish checking all indices without finding a match, we return -1.

This approach is correct because it explicitly tests every candidate index in increasing order. Since we return the first valid one encountered, the returned index is guaranteed to be the smallest valid index.

Key Insight

The problem is already asking us to examine mirrored positions. There is no need for any extra data structure, preprocessing, or nested loops.

Each index can be checked independently in constant time. Since we only need the first valid index, we can scan from left to right and stop immediately when a match is found.

This yields a simple linear solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Check every index and compare with its mirror
Optimal	O(n)	O(1)	Same idea, linear scan with early return

In this problem, the brute force approach is already optimal because each position only needs one comparison.

Algorithm Walkthrough

1. Let n be the length of the string.
2. Iterate through every index i from 0 to n - 1.
3. For each index, compute the mirrored position as n - i - 1.
4. Compare s[i] and s[n - i - 1].
5. If the two characters are equal, immediately return i because we are scanning from left to right, so this is the smallest valid index.
6. If the loop finishes without finding any match, return -1.

Why it works

The algorithm checks every possible index in increasing order. An index is valid exactly when s[i] == s[n - i - 1]. Since the scan proceeds from left to right and returns immediately upon finding a valid index, the first returned index is necessarily the smallest valid index. If no valid index exists, every candidate has been examined and rejected, so returning -1 is correct.

Python Solution

class Solution:
    def firstMatchingIndex(self, s: str) -> int:
        n = len(s)

        for i in range(n):
            if s[i] == s[n - i - 1]:
                return i

        return -1

The implementation begins by storing the string length in n.

The loop visits every index from left to right. For each position, it computes the mirrored index implicitly using n - i - 1 and compares the corresponding characters.

As soon as a matching pair is found, the function returns that index. Because the traversal order is increasing, this guarantees the smallest valid index.

If the loop completes without returning, no matching mirrored pair exists, so the function returns -1.

Go Solution

func firstMatchingIndex(s string) int {
	n := len(s)

	for i := 0; i < n; i++ {
		if s[i] == s[n-i-1] {
			return i
		}
	}

	return -1
}

The Go implementation follows exactly the same logic as the Python version.

Since the string contains only lowercase English letters, indexing a Go string by byte is safe because every character occupies exactly one byte. No special Unicode handling is necessary.

There are no concerns about integer overflow because n <= 100.

Worked Examples

Example 1

Input: s = "abcacbd"

n = 7

i	Mirror Index (n-i-1)	s[i]	s[mirror]	Match?
0	6	a	d	No
1	5	b	b	Yes

The first matching index is 1.

Output: 1

Example 2

Input: s = "abc"

n = 3

i	Mirror Index (n-i-1)	s[i]	s[mirror]	Match?
0	2	a	c	No
1	1	b	b	Yes

The first valid index is 1.

Output: 1

Example 3

Input: s = "abcdab"

n = 6

i	Mirror Index (n-i-1)	s[i]	s[mirror]	Match?
0	5	a	b	No
1	4	b	a	No
2	3	c	d	No
3	2	d	c	No
4	1	a	b	No
5	0	b	a	No

No valid index exists.

Output: -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is checked once
Space	O(1)	Only a few variables are used

The algorithm performs exactly one comparison for each index in the string. Therefore the running time grows linearly with the string length. No auxiliary data structures are allocated, so the extra space usage remains constant.

Test Cases

sol = Solution()

assert sol.firstMatchingIndex("abcacbd") == 1  # provided example
assert sol.firstMatchingIndex("abc") == 1      # center character matches itself
assert sol.firstMatchingIndex("abcdab") == -1  # no mirrored match exists

assert sol.firstMatchingIndex("a") == 0        # single-character string
assert sol.firstMatchingIndex("aa") == 0       # first pair matches immediately
assert sol.firstMatchingIndex("ab") == -1      # smallest even-length no-match case

assert sol.firstMatchingIndex("aba") == 0      # first and last characters match
assert sol.firstMatchingIndex("abcba") == 0    # palindrome
assert sol.firstMatchingIndex("abcca") == 0    # first pair matches

assert sol.firstMatchingIndex("abcdc") == 2    # only center position matches
assert sol.firstMatchingIndex("abcdefg") == 3  # odd length, center is first match

assert sol.firstMatchingIndex("abccba") == 0   # even-length palindrome
assert sol.firstMatchingIndex("abcddcba") == 0 # longer palindrome

Test Summary

Test	Why
"abcacbd"	Provided example with answer before center
"abc"	Odd length, center matches itself
"abcdab"	No valid index exists
"a"	Minimum length input
"aa"	Immediate match at index 0
"ab"	Smallest even-length failure case
"aba"	Matching outer characters
"abcba"	Odd-length palindrome
"abcca"	Match occurs at first position
"abcdc"	Only center position works
"abcdefg"	Center is first valid index
"abccba"	Even-length palindrome
"abcddcba"	Larger palindrome

Edge Cases

Single Character String

When the string length is 1, the only index is 0. Its mirrored position is also 0, so the character is compared with itself. The condition is always true, and the algorithm correctly returns 0.

Odd-Length Strings

For any odd-length string, the middle position satisfies i = n - i - 1. This means the character is compared with itself and must match. A common mistake is to only check half the string and accidentally skip the center position. The implementation checks every index, so the center is naturally handled.

No Matching Mirrored Pair

Some strings contain no matching symmetric positions. For example, "abcdab" has mismatches for every comparison. The algorithm examines all indices and only returns a value when a match is found. Therefore it correctly returns -1 after exhausting the search.

Match at the First Position

Strings such as "aa" or "abcba" have matching outermost characters. Since the problem asks for the smallest valid index, returning immediately upon finding the first match is essential. The implementation scans from left to right and exits as soon as a valid index is discovered, guaranteeing the correct smallest answer.