Skip to content

3884. First Matching Character From Both Ends

Description

You are given a string s of length n consisting of lowercase English letters.

Return the smallest index i such that s[i] == s[n - i - 1].

If no such index exists, return -1.

Β 

Example 1:

Input: s = "abcacbd"

Output: 1

Explanation:

At index i = 1, s[1] and s[5] are both 'b'.

No smaller index satisfies the condition, so the answer is 1.

Example 2:

Input: s = "abc"

Output: 1

Explanation:

​​​​​​​At index i = 1, the two compared positions coincide, so both characters are 'b'.

No smaller index satisfies the condition, so the answer is 1.

Example 3:

Input: s = "abcdab"

Output: -1

Explanation:

​​​​​​​For every index i, the characters at positions i and n - i - 1 are different.

Therefore, no valid index exists, so the answer is -1.

Β 

Constraints:

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

Solutions

Solution 1: Simulation

We iterate over the first half of the string \(s\). For each index \(i\), we check whether the characters at position \(i\) and position \(n - i - 1\) are equal. If they are, we return index \(i\). If no such index is found after the iteration, we return -1.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    def firstMatchingIndex(self, s: str) -> int:
        for i in range(len(s) // 2 + 1):
            if s[i] == s[-i - 1]:
                return i
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int firstMatchingIndex(String s) {
        int n = s.length();
        for (int i = 0; i < n / 2 + 1; ++i) {
            if (s.charAt(i) == s.charAt(n - i - 1)) {
                return i;
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int firstMatchingIndex(string s) {
        int n = s.size();
        for (int i = 0; i < n / 2 + 1; ++i) {
            if (s[i] == s[n - i - 1]) {
                return i;
            }
        }
        return -1;
    }
};

1
2
3
4
5
6
7
8
9
func firstMatchingIndex(s string) int {
    n := len(s)
    for i := 0; i < n/2+1; i++ {
        if s[i] == s[n-i-1] {
            return i
        }
    }
    return -1
}

1
2
3
4
5
6
7
8
9
function firstMatchingIndex(s: string): number {
    const n = s.length;
    for (let i = 0; i < Math.floor(n / 2) + 1; i++) {
        if (s[i] === s[n - i - 1]) {
            return i;
        }
    }
    return -1;
}

Comments