Find First Palindromic String in the Array

easy array two pointers string

Problem

Given an array of strings words, return the first palindromic string. If no palindromic string exists, return "".

Inputwords = ["abc", "car", "ada", "racecar", "cool"]

Output"ada"

For each word, check with two pointers walking inward. "ada" is the first palindrome.

words (comma-separated)

def first_palindrome(words):
    for w in words:
        l, r = 0, len(w) - 1
        ok = True
        while l < r:
            if w[l] != w[r]:
                ok = False
                break
            l += 1
            r -= 1
        if ok:
            return w
    return ""

function firstPalindrome(words) {
  for (const w of words) {
    let l = 0, r = w.length - 1;
    let ok = true;
    while (l < r) {
      if (w[l] !== w[r]) { ok = false; break; }
      l++;
      r--;
    }
    if (ok) return w;
  }
  return "";
}

class Solution {
    public String firstPalindrome(String[] words) {
        for (String w : words) {
            int l = 0, r = w.length() - 1;
            boolean ok = true;
            while (l < r) {
                if (w.charAt(l) != w.charAt(r)) { ok = false; break; }
                l++;
                r--;
            }
            if (ok) return w;
        }
        return "";
    }
}

string firstPalindrome(vector<string>& words) {
    for (const string& w : words) {
        int l = 0, r = (int) w.size() - 1;
        bool ok = true;
        while (l < r) {
            if (w[l] != w[r]) { ok = false; break; }
            l++;
            r--;
        }
        if (ok) return w;
    }
    return "";
}

Explanation

We want the first word in the list that reads the same forwards and backwards. So we check the words in order and return as soon as one passes the palindrome test.

To test a single word, use two pointers: l starts at the front and r at the back. Compare w[l] with w[r]. If they ever differ, the word is not a palindrome, so we stop early. If they match, move both pointers inward and repeat.

When l meets or passes r, every mirrored pair matched, so the word is a palindrome and we return it immediately.

Example: words = ["abc", "car", "ada", "racecar", "cool"]. "abc" fails (a ≠ c), "car" fails (c ≠ r), but "ada" works: outer a = a, then the pointers meet in the middle. So we return "ada".

If we finish the whole list without finding any palindrome, we return the empty string "".

Time: O(N · L) Space: O(1)