Find First Palindromic String in the Array

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

Given an array of strings words, return the first palindromic string in the array. A string is palindromic if it reads the same forward and backward.

If there is no such string, return an empty string "".

A string is a palindrome when it has the same sequence of characters when read from left-to-right and right-to-left.

• Examples
• Constraints
• Iterative Check with Built-in Reverse
• Two Pointers

Examples

Example 1:

Input: words = ["abc","car","ada","racecar","cool"]
Output: "ada"
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first one.

Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"

Example 3:

Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists only of lowercase English letters.

Iterative Check with Built-in Reverse

Intuition The simplest way to check if a string is a palindrome is to compare it with its reverse. We iterate through the array and return the first word that matches its reversed version.

Steps

• Iterate through each word in the input array.
• For each word, create a reversed copy of the string.
• Compare the original word with the reversed copy.
• If they are equal, return the word immediately.
• If the loop finishes without finding a match, return an empty string.

class Solution:
    def firstPalindrome(self, words: list[str]) -> str:
        for word in words:
            if word == word[::-1]:
                return word
        return ""

Complexity

• Time: O(N * L), where N is the number of words and L is the maximum length of a word. Reversing a string takes O(L) time.
• Space: O(L) to store the reversed string.
• Notes: This approach is very readable and leverages built-in language features effectively.

Two Pointers

Intuition Instead of creating a new reversed string, we can check for a palindrome in place using two pointers. One pointer starts at the beginning and the other at the end, moving towards the center.

Steps

• Iterate through each word in the input array.
• Initialize two pointers, left at 0 and right at word.length - 1.
• While left is less than right:
  • If the character at left does not equal the character at right, the word is not a palindrome; break the loop.
  • Increment left and decrement right.
• If the pointers cross or meet without a mismatch, return the word.
• If the loop finishes without finding a match, return an empty string.

class Solution:
    def firstPalindrome(self, words: list[str]) -> str:
        for word in words:
            l, r = 0, len(word) - 1
            is_palindrome = True
            while l < r:
                if word[l] != word[r]:
                    is_palindrome = False
                    break
                l += 1
                r -= 1
            if is_palindrome:
                return word
        return ""

Complexity

• Time: O(N * L), where N is the number of words and L is the maximum length of a word. In the worst case, we compare half the characters of each word.
• Space: O(1), as we only use pointers for comparison and do not allocate extra space for a new string.
• Notes: This is the most space-efficient approach as it avoids creating a copy of the string.