Matching Extremes — Problem Statement & Solution Guide
Problem Description
Given a string s of even length, calculate the number of matching character pairs at symmetric positions by comparing characters from the outside in.
Examples
Input
abccba
Output
2
Explanation: Step-by-step: Given string 'abccba', we compare characters from the outside in. 'a' at index 0 matches 'a' at index 4, 'b' at index 1 matches 'b' at index 3. Therefore, the number of matching character pairs is 2.
Input
abcdcba
Output
4
Explanation: Step-by-step: Given string 'abcdcba', we compare characters from the outside in. 'a' at index 0 matches 'a' at index 6, 'b' at index 1 matches 'b' at index 5, 'c' at index 2 matches 'c' at index 4, 'd' at index 3 matches 'd' at index 3. Therefore, the number of matching character pairs is 4.
Constraints
- 2 <= s.length <= 10^5
- s.length % 2 == 0
- s consists only of lowercase English letters.
Optimal Approach & Strategy
Using the two-pointer technique, we can initialize one pointer at the start and one at the end of the string. We compare the characters at these pointers, count the matches, and move both pointers toward the center. This solves the problem in a single pass with O(1) auxiliary space.
Brute Force Approach
The naive approach involves splitting the string in half, reversing the second half, and comparing the characters of both halves element-by-element. This approach requires extra memory to store the reversed substring, resulting in O(N) auxiliary space.
Verified Code Solutions
function matchingExtremes(s) {
let count = 0;
for (let i = 0; i < s.length / 2; i++) {
if (s[i] === s[s.length - 1 - i]) {
count++;
}
}
return count;
}class Solution {
public:
int matchingExtremes(string s) {
int count = 0;
for (int i = 0; i < s.length() / 2; i++) {
if (s[i] == s[s.length() - 1 - i]) {
count++;
}
}
return count;
}
};class Solution {
public int matchingExtremes(String s) {
int count = 0;
for (int i = 0; i < s.length() / 2; i++) {
if (s.charAt(i) == s.charAt(s.length() - 1 - i)) {
count++;
}
}
return count;
}
}def matching_extremes(s):
count = 0
for i in range(len(s) // 2):
if s[i] == s[len(s) - 1 - i]:
count += 1
return countfunction matchingExtremes(s) {
let count = 0;
for (let i = 0; i < s.length / 2; i++) {
if (s[i] === s[s.length - 1 - i]) {
count++;
}
}
return count;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.