Matching Extremes — Problem Statement & Solution Guide
Problem Description
Given a string s whose length is an even integer, determine how many pairs of characters are equal when the string is examined from both ends toward the center. For each index i from 0 to |s|/2 − 1, compare the character at position i with the character at position |s| − 1 − i. Count the number of indices where these two characters are identical. The result is the total number of matching symmetric pairs.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Matching Extremes"
WHY DOES IT MATTER?
Symmetric pairwise comparison is a foundational pattern for palindrome detection, DNA sequence analysis, and error‑checking in communication protocols. Mastering this pattern helps engineers quickly recognize when a problem reduces to a simple two‑pointer scan, avoiding unnecessary complexity.
OPTIMIZATION CHALLENGE
The key insight is that each character is involved in only one comparison, so you can eliminate nested loops and replace them with a single linear pass using two pointers that converge, reducing time from quadratic to linear.
REAL-WORLD CONNECTION
Consider a distributed storage system that replicates data across two mirrored nodes. To verify consistency, you compare each block on node A with the corresponding block on node B moving from the outermost blocks inward—exactly the same logical operation as this string problem.
During an interview, write the two‑pointer loop first, then immediately add the counter increment inside the conditional. This keeps the code short, avoids off‑by‑one errors, and demonstrates that you understand both the algorithm and its implementation details.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the count of symmetric character matches in a string of even length. By definition, for each index i in the first half of the string we compare s[i] with its mirror s[n‑1‑i]; this is a classic two‑pointer scan from both ends toward the centre. A naive solution might iterate over all possible pairs, leading to O(n^2) work, which quickly becomes infeasible for large inputs (n up to 10^6 or more). The optimal paradigm leverages the fact that each character participates in exactly one comparison, allowing a single linear pass with two pointers that move inward simultaneously. This yields O(n) time while using only constant extra space, which is the optimal bound for any algorithm that must inspect each character at least once.
The underlying algorithmic pattern is a "pairwise symmetric scan" often seen in palindrome checks, array reversal, and mirror‑image problems. Because the input size is guaranteed to be even, we never need to handle a middle unpaired character, simplifying the loop condition to i < n/2. The solution’s correctness follows from a direct bijection between each index i in the first half and its counterpart n‑1‑i in the second half; counting matches is therefore just a matter of incrementing a counter whenever the two characters are equal.
Interview Questions on This Problem
Q1How would you modify the solution if the string length could be odd and you needed to ignore the middle character?
The algorithm remains the same; you simply iterate while i < n/2 (integer division). For odd n, the middle character at index n/2 is never compared, which naturally satisfies the requirement.
Q2Can you compute the same matching count without using explicit indices, e.g., using built‑in language functions?
Yes. In many languages you can reverse the string and then iterate over zip(s, reversed_s) for the first n/2 pairs, counting where the characters are equal. This still runs in O(n) time and O(1) additional space if the reversal is done in‑place or via two‑pointer swapping.
Q3What is the time‑space trade‑off if you were asked to return the list of matching indices instead of just the count?
You would need O(k) extra space to store the matching indices, where k is the number of matches (k ≤ n/2). The time remains O(n) because you still perform a single linear scan.
Examples
Input
abccba
Output
3
Explanation: Length is 6. Pairs: (0,5): a==a → match; (1,4): b==b → match; (2,3): c==c → match. Total matches = 3.
Input
abcdba
Output
2
Explanation: Length is 6. Pairs: (0,5): a==a → match; (1,4): b==b → match; (2,3): c!=d → no match. Total matches = 2.
Input
aabbccdd
Output
0
Explanation: Length is 8. Pairs: (0,7): a!=d; (1,6): a!=d; (2,5): b!=c; (3,4): b!=c. No matches, so output is 0.
Input
zzzzzz
Output
3
Explanation: All characters are 'z'. Every pair matches: (0,5), (1,4), (2,3). Total matches = 3.
Input
abxyba
Output
2
Explanation: Length is 6. Pairs: (0,5): a==a → match; (1,4): b==b → match; (2,3): x!=y → no match. Total matches = 2.
Constraints
- 1 <= |s| <= 100000
- |s| is even
- s consists only of lowercase English letters
Optimal Approach & Strategy
Use two pointers moving inward from both ends, compare each mirrored pair exactly once, and count matches. This runs in linear time with constant extra memory.
Brute Force Approach
Loop over every possible i and j pair and compare s[i] with s[j] to find matches, resulting in O(n^2) time. This checks many unnecessary pairs because each character only needs one comparison.
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
let s = input;
let n = s.length;
let count = 0;
for(let i = 0; i < n/2; i++) {
if(s[i] === s[n-1-i]) count++;
}
console.log(count);#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
if(!(cin >> s)) return 0;
int n = s.size();
int count = 0;
for(int i = 0; i < n/2; ++i) {
if(s[i] == s[n-1-i]) count++;
}
cout << count << "\n";
return 0;
}import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int n = s.length();
int count = 0;
for(int i = 0; i < n/2; i++) {
if(s.charAt(i) == s.charAt(n-1-i)) count++;
}
System.out.println(count);
}
}import sys
def main():
s = sys.stdin.readline().strip()
n = len(s)
count = 0
for i in range(n//2):
if s[i] == s[n-1-i]:
count += 1
print(count)
if __name__ == "__main__":
main()const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim();
let s = input;
let n = s.length;
let count = 0;
for(let i = 0; i < n/2; i++) {
if(s[i] === s[n-1-i]) count++;
}
console.log(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.