Watch 10 video solutions for Find First Palindromic String in the Array, a easy level problem involving Array, Two Pointers, String. This walkthrough by NeetCodeIO has 11,882 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1001 <= words[i].length <= 100words[i] consists only of lowercase English letters.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 | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n * m) | O(1) | Best general solution when checking palindromes efficiently without extra memory |
| String Reversal Method | O(n * m) | O(m) | Useful when language provides simple built-in string reversal and memory usage is not critical |