Find First Palindromic String in the Array solution and explanation
9 more videos on this problem
Find First Palindromic String in the Array - Leetcode 2108 - PythonNeetCodeIO · 5:34 · 12K views
Leetcode | 2108. Find First Palindromic String in the Array | Easy | Java SolutionDeveloper Docs · 6:19 · 2K views
LeetCode 2108 Find First Palindromic String in the Array | Amazon | Very Easy | String | PalindromeCode Harmony · 8:25 · 1K views
2108. Find First Palindromic String in the Array (Leetcode Easy)Programming Live with Larry · 1:46 · 725 views
LeetCode 2108 : Find First Palindromic String in the Array | Solution in JAVAAmit Manjarly · 7:10 · 452 views
LeetCode 2108 : Find First Palindromic String in the Array | Solution in C++Amit Manjarly · 6:17 · 452 views
2108 Find First Palindromic String in the ArrayMath Geeks · 0:43 · 147 views
HOW TO Find First Palindromic String in the Array - Leetcode 2108Lit Code · 7:07 · 112 views
Find First Palindromic String in the Array LeetCode - JavaCode with Katie · 6:20 · 75 views
Find First Palindromic String in the Array - Leetcode 2108 (Python)nexTRIE · 3:17 · 52 views
The problem
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.
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.
def is_palindrome(s):
return s == s[::-1]
def first_palindrome(words):
for word in words:
if is_palindrome(word):
return word
return ""public class Solution {
public String firstPalindrome(String[] words) {
for (String word : words) {
if (isPalindrome(word)) {
return word;
}
}
return "";
}
private boolean isPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isPalindrome(const string &s) {
int i = 0, j = s.size() - 1;
while (i < j) {
if (s[i++] != s[j--]) {
return false;
}
}
return true;
}
string firstPalindrome(vector<string>& words) {
for (const auto &word : words) {
if (isPalindrome(word)) {
return word;
}
}
return "";
}function isPalindrome(s) {
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left++] !== s[right--]) {
return false;
}
}
return true;
}
function firstPalindrome(words) {
for (const word of words) {
if (isPalindrome(word)) {
return word;
}
}
return "";
}#include <stdio.h>
#include <string.h>
int isPalindrome(char *s) {
int i = 0, j = strlen(s) - 1;
while (i < j) {
if (s[i] != s[j]) return 0;
i++;
j--;
}
return 1;
}
char* firstPalindrome(char** words, int wordsSize) {
for (int i = 0; i < wordsSize; i++) {
if (isPalindrome(words[i])) {
return words[i];
}
}
return "";
}public class Solution {
public string FirstPalindrome(string[] words) {
foreach (var word in words) {
if (IsPalindrome(word)) {
return word;
}
}
return "";
}
private bool IsPalindrome(string s) {
int i = 0, j = s.Length - 1;
while (i < j) {
if (s[i++] != s[j--]) {
return false;
}
}
return true;
}
}The function is_palindrome checks if a string is a palindrome by comparing it to its reverse. The first_palindrome function iterates through the list to locate and return the first palindromic string found.
Time Complexity: O(n * m), where n is the number of words, and m is the length of each word.
Space Complexity: O(1) as only constant space is used additionally.
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.
def first_palindrome(words):
for word in words:
if word == word[::-1]:
return word
return ""public class Solution {
public String firstPalindrome(String[] words) {
for (String word : words) {
if (word.equals(new StringBuilder(word).reverse().toString())) {
return word;
}
}
return "";
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
string reverse(const string &s) {
string rev = s;
reverse(rev.begin(), rev.end());
return rev;
}
string firstPalindrome(vector<string>& words) {
for (const auto &word : words) {
if (word == reverse(word)) {
return word;
}
}
return "";
}function firstPalindrome(words) {
for (const word of words) {
const reversedWord = word.split('').reverse().join('');
if (word === reversedWord) {
return word;
}
}
return "";
}#include <stdio.h>
#include <string.h>
char* reverse(const char *s) {
int len = strlen(s);
char* rev = (char*)malloc((len + 1) * sizeof(char));
for (int i = 0; i < len; i++) {
rev[i] = s[len - i - 1];
}
rev[len] = '\0';
return rev;
}
char* firstPalindrome(char** words, int wordsSize) {
for (int i = 0; i < wordsSize; i++) {
char* rev = reverse(words[i]);
if (strcmp(words[i], rev) == 0) {
free(rev);
return words[i];
}
free(rev);
}
return "";
}public class Solution {
public string FirstPalindrome(string[] words) {
foreach (var word in words) {
char[] charArray = word.ToCharArray();
Array.Reverse(charArray);
if (word.Equals(new string(charArray))) {
return word;
}
}
return "";
}
}This Python solution reverses each word and compares it to itself. If they're equal, it is palindromic, and the word is returned.
Time Complexity: O(n * m), where n is the number of words and m is the average length of words.
Space Complexity: O(m) for reversed string storage.
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).
function firstPalindrome(words: string[]): string {
return words.find(w => w === w.split('').reverse().join('')) || '';
}func firstPalindrome(words []string) string {
for _, w := range words {
ok := true
for i, j := 0, len(w)-1; i < j && ok; i, j = i+1, j-1 {
if w[i] != w[j] {
ok = false
}
}
if ok {
return w
}
}
return ""
}impl Solution {
pub fn first_palindrome(words: Vec<String>) -> String {
for w in words {
if w == w.chars().rev().collect::<String>() {
return w;
}
}
String::new()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n * m), where n is the number of words, and m is the length of each word. |
| String Reversal Method | Time Complexity: O(n * m), where n is the number of words and m is the average length of words. |
| Simulation | – |
Complexity analysis
| 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 |
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.