First Matching Character From Both Ends - Solution & Explanation

Problem Overview: You are given a string and need to find the first character that matches when comparing characters from the left and right ends simultaneously. Start at both ends of the string and move inward until a pair of characters is the same. Return that character when the first match occurs.

Approach 1: Brute Force Pair Checking (O(n) time, O(1) space)

The straightforward idea is to compare characters symmetrically from the beginning and end of the string. For every index i, check whether s[i] == s[n - 1 - i]. The first pair that satisfies this condition gives the answer. This works because the problem only cares about mirrored positions from both ends. The algorithm simply iterates through half of the string and performs a constant-time comparison for each pair.

This approach is essentially a direct simulation of the problem statement. No additional data structures are needed. The time complexity is O(n) because at most n/2 comparisons are performed, and the space complexity remains O(1).

Approach 2: Two Pointers Simulation (O(n) time, O(1) space)

A cleaner implementation uses the classic two pointers technique. Initialize one pointer at the start of the string (left = 0) and another at the end (right = n - 1). While left < right, compare the characters at both pointers. If they match, return that character immediately. Otherwise, move both pointers inward (left++, right--) and continue.

This approach directly models the idea of scanning from both ends simultaneously. It avoids any unnecessary checks and stops as soon as a valid pair is found. The algorithm touches each mirrored pair only once, so the time complexity is O(n) with constant O(1) space.

This pattern shows up frequently in string problems where comparisons happen symmetrically from both sides. It is essentially a lightweight simulation of the process described in the problem.

Recommended for interviews: The two-pointer simulation is what interviewers typically expect. It is simple, readable, and clearly communicates the intent of scanning from both ends. The brute-force pair comparison demonstrates understanding of the mirrored indexing idea, but the explicit two-pointer version is cleaner and easier to reason about during an interview.