easyStringsPattern: Two Pointers
Symmetry Score of a String Solution
Problem Statement
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. Specifically, you compare the character at the left pointer i (starting at 0) with the character at the right pointer j (starting at s.length - 1). If s[i] equals s[j], it counts as a match. After each comparison, increment i and decrement j, stopping when the pointers meet or cross.
Examples
Example 1:
Input:s = "ababa"
Output:2
Explanation: We compare from the outside in: 1. s[0] ('a') and s[4] ('a') match. 2. s[1] ('b') and s[3] ('b') match. The pointers meet at s[2] ('a'), so we stop. There are 2 matching pairs.
Example 2:
Input:s = "abcde"
Output:0
Explanation: We compare: 1. s[0] ('a') and s[4] ('e') do not match. 2. s[1] ('b') and s[3] ('d') do not match. The pointers meet at s[2] ('c'), so we stop. There are 0 matching pairs.
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).
Time: O(N) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.