Problem

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.

Constraints:

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

Examples:

• s = "abcacbd" → 1. s[1] and s[5] are both 'b', and no smaller index satisfies the condition.
• s = "abc" → 1. At i = 1 the two compared positions coincide, so both characters are 'b'.
• s = "abcdab" → -1. For every index i, the characters at positions i and n - i - 1 are different.

Walkthrough

Full iteration

In this problem we don't need to worry about normalising the input, they're all lowercase so we can do a direct comparison. We'll want to iterate through the characters in the string, returning the index if we find a match, with -1 as a fallback if we don't.

As usual with these problems we'll start very simply and just iterate over the whole string. As we're starting from the left, that'll be the smallest index so we can just stop whenever we find a solution.

1
2
3
4
5
6
7
8

class Solution:
  def firstMatchingIndex(self, s: str) -> int:
    n = len(s)
    for idx in range(n):
      if s[idx] == s[n - idx - 1]:
        return idx
    # If we didn't return there is no solution
    return -1

Submission result

Stopping half way

Now we've got the base case working we can extend it. Once we've passed the half way point there's no point carrying on because if we are going to find a solution we would already have found it. First consider a string of even length 'abcdef'. If you trace out the comparisons you'll do, you have a->f, b->e, c->d. Then when you pass half way you've just got them in reverse: d->c, e->b, f->a. What about if the string is odd length: 'abcde'. In this case we will always have a solution and worst case it'll be the middle element. If we follow this through again: a->e, b->d, c->c. You can see on the odd length string you always compare the middle element to itself.

In python don't forget the indexes start at 0 and range isn't inclusive of the value passed. So, we'll start with n // 2. We use // rather than / as that's integer division. This would give us for length 4: range(2) which is [0, 1]. Excellent, just what we want.

For an odd length list, say, 3 we'd have 3 // 2 which is 1. That's not enough! So we'll have to add one to this: (n + 1) // 2. In the odd length you get (3 + 1) // 2 == 2 and in the even case we have (4 + 1) // 2 == 2 so they both work.

It's understanding the edge cases we have here that's key to this problem.

1
2
3
4
5
6
7
8

class Solution:
  def firstMatchingIndex(self, s: str) -> int:
    n = len(s)
    for idx in range((n + 1) // 2):
      if s[idx] == s[n - idx - 1]:
        return idx
    # If we didn't return there is no solution
    return -1

Submission result

This solution still has complexity O(n) but we check half as many elements, so it's clearly superior.