Skip to main content
Talentd

Find First Palindromic String in the Array - Solution & Explanation

EasyArrayTwo PointersString15 min read
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive an array of lowercase strings. The task is to return the first string that reads the same forward and backward. If none of the words are palindromes, return an empty string.

Approach 1: Two-Pointer Technique (O(n * m) time, O(1) space)

This approach checks each word using the classic palindrome pattern with two pointers. For every string in the array, place one pointer at the beginning and another at the end. Move both pointers inward while the characters match. If a mismatch occurs, the string is not a palindrome. If the pointers cross without mismatches, the word is a palindrome and you immediately return it.

The key insight is that palindrome verification only requires comparing mirrored characters. This avoids creating extra strings or data structures. Since each word of length m may require up to m/2 comparisons and you may scan up to n words, the total complexity becomes O(n * m). Space usage stays O(1) because the check happens in-place. This method is the most efficient and is commonly used when working with two pointers and string problems.

Approach 2: String Reversal Method (O(n * m) time, O(m) space)

Another straightforward approach is reversing each word and comparing it with the original. Iterate through the array, create a reversed version of the current string, and check if it matches the original string. If both are equal, the word is a palindrome and you return it immediately.

This method is easy to implement in languages with built-in string reversal utilities. However, reversing a string requires allocating additional memory proportional to its length. Each reversal takes O(m) time and O(m) space. While the overall time complexity remains O(n * m), the extra memory makes it slightly less optimal than the two-pointer technique.

Recommended for interviews: Interviewers typically expect the two-pointer approach. It demonstrates a strong grasp of palindrome properties and avoids unnecessary memory allocation. The reversal approach is acceptable as a quick baseline, but the in-place pointer comparison shows deeper algorithmic awareness and better space efficiency.

Approach 1: Two-Pointer Technique

This approach involves checking each string using a two-pointer technique. You set one pointer at the start and one at the end of the string and compare characters. If all characters match until the pointers cross, the string is a palindrome.

The function isPalindrome uses two pointers to check each character from both ends of a string. If they match all through, the string is a palindrome. The firstPalindrome function iterates through the list of words and returns the first palindromic string it finds.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1) because it uses constant space.

Try this approach in the editor →

Approach 2: String Reversal Method

This method leverages string reversal to check if a word is a palindrome. You can reverse the string and compare it with the original; if they are the same, it's a palindrome.

The reverse function creates and returns a reversed version of the input string. In firstPalindrome, for each word in the array, it checks if the word equals its reversed counterpart, indicating it's a palindrome, and returns it.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the number of words and m is the length of words.
Space Complexity: O(m) due to the additional string for reversal.

Try this approach in the editor →

Approach 3: 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.

To determine if a string is a palindrome, we can use two pointers, one pointing to the start and the other to the end of the string, moving towards the center, and checking if the corresponding characters are equal. If, after traversing the entire string, no unequal characters are found, then the string is a palindrome.

The time complexity is O(L), where L is the sum of the lengths of all strings in the array words. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two-Pointer Technique

Time Complexity: O(n * m), where n is the number of words and m is the average length of the words.
Space Complexity: O(1) because it uses constant space.

String Reversal Method

Time Complexity: O(n * m), where n is the number of words and m is the length of words.
Space Complexity: O(m) due to the additional string for reversal.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer TechniqueO(n * m)O(1)Best general solution when checking palindromes efficiently without extra memory
String Reversal MethodO(n * m)O(m)Useful when language provides simple built-in string reversal and memory usage is not critical

Video Solution

Find First Palindromic String in the Array - Leetcode 2108 - Python • NeetCodeIO • 12,034 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find First Palindromic String in the Array easy or hard?
Find First Palindromic String in the Array is classified as an Easy problem. It focuses on basic string manipulation and array iteration. The key skill being tested is recognizing the palindrome property and applying a simple two-pointer comparison efficiently.
Find First Palindromic String in the Array Python/Java solution
The solution iterates through each word and checks whether it is a palindrome. In Python, this can be done with a two-pointer loop or by comparing the string to its reverse using slicing. In Java, two indices move inward from both ends of the string until a mismatch occurs or the pointers cross.
How to solve Find First Palindromic String in the Array in O(n)?
Strict O(n) is not possible because each string must be inspected character by character. The optimal practical complexity is O(n * m). Iterate through the array and use a two-pointer palindrome check for each word. Return the first word where all mirrored characters match.
What is the best approach for Find First Palindromic String in the Array?
The two-pointer technique is the most efficient approach. For each word, compare characters from the left and right ends while moving inward. This checks whether the string is a palindrome without creating additional strings. The overall complexity is O(n * m) time and O(1) space, where n is the number of words and m is the maximum word length.
Is Find First Palindromic String in the Array asked at Google/Amazon/Meta?
Palindrome-related string problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may not always appear, it tests common fundamentals such as two-pointer techniques, string traversal, and early termination during iteration.
What data structure is used in Find First Palindromic String in the Array?
The problem primarily uses an array of strings as input. The algorithm itself relies on pointer manipulation within each string rather than additional data structures. The two-pointer technique allows checking palindromes directly inside the string with constant extra space.
What is the time complexity of Find First Palindromic String in the Array?
The time complexity is O(n * m). You may need to examine every string in the array (n words), and verifying whether a word is a palindrome can take up to m/2 comparisons where m is the word length. Space complexity can be O(1) with the two-pointer approach or O(m) if string reversal is used.

Ready to solve this problem?

Practice Find First Palindromic String in the Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Valid Palindrome