#2108

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Find First Palindromic String in the Array

Return the first palindromic string from an array of words or an empty string if none exists.

Problem Statement

You are given an array of strings called words. You need to find the first string that is palindromic. If no such string exists, return an empty string.

A string is considered palindromic if it reads the same forward and backward. For example, 'ada' is palindromic, but 'abc' is not.

Examples

Example 1

Input: words = ["abc","car","ada","racecar","cool"]

Output: "ada"

The first string that is palindromic is "ada". Note that "racecar" is also palindromic, but it is not the first.

Example 2

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

Output: "racecar"

The first and only string that is palindromic is "racecar".

Example 3

Input: words = ["def","ghi"]

Output: ""

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.

Solution Approach

Two-pointer Scanning

Use a two-pointer approach for each word. One pointer starts from the beginning and the other from the end of the word. Check if the characters at both pointers match. If they do for the entire word, it's palindromic.

Iterate Through Words

Iterate through the words array in order. For each word, check if it is palindromic. As soon as you find a palindromic word, return it. If no palindromic word is found, return an empty string.

Return the Result

Once you find the first palindromic string, return it immediately. If you finish checking all words without finding a palindrome, return an empty string.

Complexity Analysis

Metric	Value
Time	O(N \cdot M)
Space	O(1)

The time complexity is O(N * M), where N is the number of words and M is the maximum length of any word. Checking if a word is palindromic takes O(M) time. The space complexity is O(1) because we are only using a constant amount of extra space for pointers.

What Interviewers Usually Probe

Look for efficient handling of string iteration.
Ensure the candidate applies the two-pointer technique correctly.
Check if the solution returns early upon finding the first palindromic word.

Common Pitfalls or Variants

Common pitfalls

Failing to iterate through the array properly.
Not returning early when the first palindromic word is found.
Incorrectly assuming that checking palindromic status is trivial without using a systematic approach like two-pointer scanning.

Follow-up variants

Return the first palindrome with specific character conditions (e.g., only vowels).
Handle larger inputs efficiently with O(N * M) time complexity.
Extend to find the longest palindromic string in the array.

FAQ

How can I find the first palindromic string in an array?

You can find the first palindromic string by using a two-pointer technique to check if each word in the array is palindromic. Return the first palindrome you encounter.

What is the time complexity of this problem?

The time complexity is O(N * M), where N is the number of words and M is the length of the longest word.

What does it mean for a string to be palindromic?

A palindromic string is one that reads the same forward and backward, such as 'madam' or 'ada'.

Can this problem be solved with a brute force approach?

Yes, but using a two-pointer approach ensures a more efficient solution by checking each word only once and stopping early if a palindrome is found.

What pattern is applied in this problem?

This problem uses a two-pointer scanning technique, which is effective for checking palindromic strings in a systematic manner.

terminal

Solution

Solution 1: Simulation

We iterate through the array `words`, for each string `w`, we determine if it is a palindrome. If it is, then we return `w`; otherwise, we continue to iterate.

1

2

3

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

Continue Practicing

#2109 adding spaces to a string #1961 check if string is a prefix of array #1898 maximum number of removable characters