Symmetry Score of a String — Problem Statement & Solution Guide
Problem Description
Given a string s, calculate its symmetry score. The symmetry score is the number of matching pairs of characters when comparing the string from its outermost boundaries moving inward. For strings of odd length, the middle character is considered a match with itself.
Examples
Input
abba
Output
2
Explanation: Step-by-step: with input 'abba', we compare 'a' at index 0 with 'a' at index 3 (match), and 'b' at index 1 with 'b' at index 2 (match), giving a total of 2 matches
Input
abcba
Output
3
Explanation: Step-by-step: with input 'abcba', we compare 'a' at index 0 with 'a' at index 4 (match), 'b' at index 1 with 'b' at index 3 (match), and 'c' at index 2 is compared with itself (match), giving a total of 3 matches
Constraints
- 1 <= s.length <= 10^5
- s consists only of lowercase English letters.
- Expected time complexity is O(N) where N is the length of the string.
- Expected auxiliary space complexity is O(1).
Optimal Approach & Strategy
The optimal approach uses the Two Pointers technique to scan the string from both outer boundaries inward. We initialize a left pointer at 0 and a right pointer at s.length - 1, comparing characters at each step. If they match, we increment our score, and then we increment the left pointer and decrement the right pointer until they meet or cross, running in O(N) time with O(1) space.
Brute Force Approach
A naive approach might involve creating a reversed copy of the string and comparing the original string characters up to the midpoint against the reversed string characters. This requires extra O(N) auxiliary space to store the reversed string, which is suboptimal compared to doing it in place.
Verified Code Solutions
function symmetryScore(s) {
let left = 0, right = s.length - 1, count = 0;
while (left < right) {
if (s[left] === s[right]) {
count++;
left++;
right--;
} else if (left === right) {
count++;
} else {
break;
}
}
return count;
}class Solution {
public int symmetryScore(String s) {
int score = 0;
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
score++;
}
left++;
right--;
}
return score;
}
}def symmetry_score(s: str) -> int:
score = 0
left, right = 0, len(s) - 1
while left < right:
if s[left] == s[right]:
score += 1
left += 1
right -= 1
return scorefunction symmetryScore(s) {
let left = 0, right = s.length - 1, count = 0;
while (left < right) {
if (s[left] === s[right]) {
count++;
left++;
right--;
} else if (left === right) {
count++;
} else {
break;
}
}
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.