Find First Palindromic String in the Array

Easy
532.

Find First Palindromic String in the Array

Find First Palindromic String in the Array is an easy coding problem on arrays, strings and two pointers, asked in Amazon and TCS interviews.

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 <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {string}
 */
var firstPalindrome = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • 1 <= words[i].length <= 100
  • words[i] consists of lowercase English letters.

Hints for Find First Palindromic String in the Array

  1. Hint 1

    Test each word in order and return at the first hit.

  2. Hint 2

    A two-pointer scan checks a palindrome in O(length) with no extra memory.

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

  1. Iterate the array in order.
  2. For each word, walk two pointers inward comparing characters.
  3. Return the word on the first successful check.
  4. 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings