First Matching Character From Both Ends

Difficulty: Easy | Acceptance: 81.80% | Paid: No Topics: Two Pointers, String

You are given a string s. Return the first character that matches when comparing the string from the beginning and the end.

Specifically, you need to compare the character at index 0 with the character at index n - 1, then index 1 with index n - 2, and so on. The first time you find a pair of characters that are equal, return that character. If no such pair exists after checking all possible pairs, return an empty string.

• Examples
• Constraints
• Two Pointers
• Reverse String

Examples

Example 1:

Input: s = "abcdcba"
Output: "a"
Explanation: s[0] = 'a' and s[6] = 'a' match. 'a' is returned.

Example 2:

Input: s = "abca"
Output: "a"
Explanation: s[0] = 'a' and s[3] = 'a' match. 'a' is returned.

Example 3:

Input: s = "abcdef"
Output: ""
Explanation: No characters match from the ends.

Constraints

1 <= s.length <= 100
s consists of lowercase English letters.

Two Pointers

Intuition We can solve this efficiently by using two pointers: one starting at the beginning (left) and one at the end (right) of the string. We move these pointers towards each other, comparing the characters at their respective positions. The first match we encounter is the answer.

Steps

• Initialize left to 0 and right to s.length - 1.
• Loop while left is less than right.
• In each iteration, check if s[left] equals s[right].
• If they are equal, return s[left] immediately.
• If not, increment left and decrement right.
• If the loop finishes without finding a match, return an empty string.

class Solution:
    def firstMatchingChar(self, s: str) -> str:
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] == s[right]:
                return s[left]
            left += 1
            right -= 1
        return ''

Complexity

• Time: O(n), where n is the length of the string. In the worst case, we traverse half the string.
• Space: O(1), as we only use two pointers for storage.
• Notes: This is the most optimal approach for this problem.

Reverse String

Intuition Another way to look at the problem is comparing the original string with its reverse. If we iterate through the original string and the reversed string simultaneously, the first index where the characters match corresponds to the first matching character from the ends.

Steps

• Create a reversed copy of the string s.
• Iterate through the indices of the string.
• Compare s[i] with reversed[i].
• If they match, return s[i].
• If the loop ends, return an empty string.

class Solution:
    def firstMatchingChar(self, s: str) -> str:
        reversed_s = s[::-1]
        for i in range(len(s)):
            if s[i] == reversed_s[i]:
                return s[i]
        return ''

Complexity

• Time: O(n), as reversing a string and iterating both take linear time.
• Space: O(n), because we need to store the reversed copy of the string.
• Notes: While conceptually simple, this uses extra space compared to the Two Pointers approach.