First Matching Character From Both Ends solution and explanation
8 more videos on this problem
3884. First Matching Character From Both Ends (Leetcode Easy)Programming Live with Larry · 1:49 · 106 views
First Matching Character From Both Ends | LeetCode 3884 | Weekly Contest 495 | Developer CoderDeveloper Coder · 5:52 · 42 views
First Matching Character From Both Ends | Leetcode 3884 | Explanation With Code | Javacodewithsitaram · 12:10 · 38 views
3884.First Matching Characters from Both the Ends|Weely Contest 495 |#leetcode #dsa #coding #lecturecodewarriortelugu · 1:07 · 34 views
First Matching Character From Both Ends | LeetCode 3884 | Easy C++ SolutionCore Logic Dev · 3:58 · 28 views
3884. First Matching Character From Both Ends | Leetcode 3884 | C++ | Hindi | Easy for BeginnersPushkar Sehrawat · 7:23 · 24 views
LeetCode Problem 3884 | First Matching Character From Both EndsRepovive TV · 1:40 · 19 views
Leetcode 3884. First Matching Character From Both Ends || Weekly Contest 495ExpertFunda · 7:51 · 9 views
LeetCode 3884 | First Matching Character From Both Ends | Easy C++ SolutionProjectForge · 4:11 · 1 view
The problem
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 <= 100sconsists of lowercase English letters.
Approach overview
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.
Solution
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).
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 -1class Solution {
public int firstMatchingIndex(String s) {
int n = s.length();
for (int i = 0; i < n / 2 + 1; ++i) {
if (s.charAt(i) == s.charAt(n - i - 1)) {
return i;
}
}
return -1;
}
}class Solution {
public:
int firstMatchingIndex(string s) {
int n = s.size();
for (int i = 0; i < n / 2 + 1; ++i) {
if (s[i] == s[n - i - 1]) {
return i;
}
}
return -1;
}
};function firstMatchingIndex(s: string): number {
const n = s.length;
for (let i = 0; i < Math.floor(n / 2) + 1; i++) {
if (s[i] === s[n - i - 1]) {
return i;
}
}
return -1;
}func firstMatchingIndex(s string) int {
n := len(s)
for i := 0; i < n/2+1; i++ {
if s[i] == s[n-i-1] {
return i
}
}
return -1
}Complexity analysis
| 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 |
Frequently asked questions
Is First Matching Character From Both Ends easy or hard?
First Matching Character From Both Ends is considered an easy problem. It mainly tests basic string traversal and understanding of the two-pointer pattern with O(n) time and O(1) space.
First Matching Character From Both Ends Python/Java solution
The solution is typically implemented with two indices scanning inward. In Python, Java, C++, Go, or TypeScript, the logic is identical: initialize left and right pointers, compare characters, and move inward until a matching pair is found.
How to solve First Matching Character From Both Ends in O(n)?
Use two pointers: one at the start and one at the end of the string. Compare the characters at both pointers. If they match, return that character; otherwise move both pointers inward and repeat until a match is found or the pointers cross.
What is the best approach for First Matching Character From Both Ends?
The two-pointer simulation approach is the best solution. Start one pointer at the beginning of the string and another at the end, compare characters, and move inward until a match is found. This method runs in O(n) time and uses O(1) extra space.
Is First Matching Character From Both Ends asked at Google/Amazon/Meta?
This specific problem is categorized as an easy string simulation question. Variants using two pointers and symmetric comparisons frequently appear in interviews at companies like Amazon, Google, and Meta because they test basic string manipulation and pointer logic.
What data structure is used in First Matching Character From Both Ends?
The problem primarily uses a string with a two-pointer technique. No additional data structures such as hash maps or stacks are required, keeping the space complexity constant.
What is the time complexity of First Matching Character From Both Ends?
The optimal solution runs in O(n) time because each mirrored pair of characters is checked at most once while scanning from both ends. The space complexity is O(1) since only a few pointer variables are used.