Find First Palindromic String in the Array

LeetCode 2231 | Difficulty: Easy

Easy

Problem Description

Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".

A string is palindromic if it reads the same forward and backward.

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.

Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "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.

Topics: Array, Two Pointers, String

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

---

Solutions

Solution 1: C# (Best: 195 ms)

Metric	Value
Runtime	195 ms
Memory	38.9 MB
Date	2022-01-08

Solution

public class Solution {
    public string FirstPalindrome(string[] words) {
        string result = words.Where(x=>IsPalindrome(x)).FirstOrDefault();
        return result == null ? "" : result; 
    }
    
    private bool IsPalindrome(string str)
    {
        int i=0,j = str.Length -1;
        while(i<j)
        {
            if(str[i++]!=str[j--])
            {
                return false;
            }
        }
        return true;
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Iterate through the elements in order. As soon as the current element is a palindrome, return it.

Hint 2: To check if an element is a palindrome, can you reverse the string?