Find First Palindromic String in the Array — Solution
Find First Palindromic String in the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find First Palindromic String in the Array is an easy coding problem on arrays, strings and two pointers, asked in Amazon and TCS interviews.
- Difficulty: Easy
- Topics: Arrays, Strings, Two Pointers
- Asked at: Amazon, TCS
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of strings words, return the first string in it that is a palindrome. If none is, return the empty string.
Example 1
Input: words = ["abc","car","ada","racecar","cool"]
Output: ada
Explanation: "ada" is the first palindrome; "racecar" is also one but comes later.
Example 2
Input: words = ["notapalindrome","racecar"]
Output: racecar
Example 3
Input: words = ["def","ghi"]
Output:
Explanation: Neither is a palindrome.
Constraints
1 <= words.length <= 1001 <= words[i].length <= 100words[i] consists of lowercase English letters.
Hints for Find First Palindromic String in the Array
Hint 1
Test each word in order and return at the first hit.
Hint 2
A two-pointer scan checks a palindrome in O(length) with no extra memory.
Hint 3
A single character is always a palindrome.
How to solve Find First Palindromic String in the Array
A linear scan with an early return: the first word that reads the same both ways is the answer.
Approach
- Iterate the array in order.
- For each word, walk two pointers inward comparing characters.
- Return the word on the first successful check.
- Return the empty string if none matched.
Why it works
Returning on the first success guarantees the earliest index, and the two-pointer check is exactly the definition of a palindrome.
Complexity
- Time —
O(total characters) - Space —
O(1) with the two-pointer check
Pitfalls
- Building a reversed copy of every word works but allocates unnecessarily.
- Returning the shortest or longest palindrome instead of the first is a misread of the problem.
Reference solution
Python
from typing import List
def firstPalindrome(words: List[str]) -> str:
for w in words:
if w == w[::-1]:
return w
return ""Java
public static String firstPalindrome(String[] words) {
for (String w : words) {
int i = 0, j = w.length() - 1;
boolean ok = true;
while (i < j) {
if (w.charAt(i) != w.charAt(j)) { ok = false; break; }
i++;
j--;
}
if (ok) return w;
}
return "";
}C++
string firstPalindrome(vector<string>& words) {
for (auto& w : words) {
int i = 0, j = (int) w.size() - 1;
bool ok = true;
while (i < j) {
if (w[i] != w[j]) { ok = false; break; }
i++;
j--;
}
if (ok) return w;
}
return "";
}JavaScript
var firstPalindrome = function(words) {
function isPal(w) {
let i = 0, j = w.length - 1;
while (i < j) {
if (w.charAt(i) !== w.charAt(j)) return false;
i++;
j--;
}
return true;
}
for (let i = 0; i < words.length; i++) {
if (isPal(words[i])) return words[i];
}
return "";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.