You are given a string s of length n consisting of lowercase English letters.
Return the smallest index i such that s[i] == s[n - i - 1].
If no such index exists, return -1.
Example 1:
Input: s = "abcacbd"
Output: 1
Explanation:
At index i = 1, s[1] and s[5] are both 'b'.
No smaller index satisfies the condition, so the answer is 1.
Example 2:
Input: s = "abc"
Output: 1
Explanation:
At index i = 1, the two compared positions coincide, so both characters are 'b'.
No smaller index satisfies the condition, so the answer is 1.
Example 3:
Input: s = "abcdab"
Output: -1
Explanation:
For every index i, the characters at positions i and n - i - 1 are different.
Therefore, no valid index exists, so the answer is -1.
Constraints:
1 <= n == s.length <= 100s consists of lowercase English letters.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.
We iterate over the first half of the string s. For each index i, we check whether the characters at position i and position n - i - 1 are equal. If they are, we return index i. If no such index is found after the iteration, we return -1.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Checking | O(n) | O(1) | When implementing the simplest mirrored comparison logic |
| Two Pointers Simulation | O(n) | O(1) | Preferred solution for scanning from both ends efficiently |
Practice First Matching Character From Both Ends with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor