Find First Palindromic String in the Array

How it works

Instead of creating a reversed copy (which uses extra space), we can check if a string is a palindrome in place using two pointers. One pointer starts at the beginning, the other at the end. If all corresponding characters match as the pointers move toward each other, the string is a palindrome. This avoids the extra memory needed to store the reversed string.

Steps

1. Iterate through each word in the array.
2. For each word, use two pointers: l at the start and r at the end.
3. While the characters at l and r are equal:
   • If l >= r, the word is a palindrome; return it.
   • Move l forward and r backward.
4. If the characters differ, move to the next word.
5. If no palindrome is found, return an empty string.

Complexity

• Time complexity: O(n * m)
• Space complexity: O(1) extra space.

Where n is the size of the string array words and m is the average length of a word in the array.

Things to watch for

Forgetting to Return an Empty String

A common mistake is forgetting to handle the case where no palindrome exists in the array. The problem requires returning an empty string "" when no palindromic string is found, not null or throwing an error. Always ensure your function has a default return statement after the loop completes.

Continuing Search After Finding the First Palindrome

Since the problem asks for the first palindromic string, you should return immediately upon finding one. A pitfall is iterating through the entire array and collecting all palindromes, then returning the first. This wastes time and misses the point of early termination, which is key to optimal performance.

from typing import List

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for w in words:
            l, r = 0, len(w) - 1
            while w[l] == w[r]:
                if l >= r:
                    return w
                l, r = l + 1, r - 1
        return ""

class Solution {
public:
    string firstPalindrome(vector<string>& words) {
        for (const string& w : words) {
            int l = 0, r = w.length() - 1;
            while (w[l] == w[r]) {
                if (l >= r) return w;
                l++;
                r--;
            }
        }
        return "";
    }
};