2108. Find First Palindromic String in the Array - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

String Manipulation - Reversing strings and comparing characters
Two Pointers - Using left and right pointers to check palindrome properties efficiently
Array Iteration - Iterating through arrays and returning early when a condition is met

1. Reverse String

Intuition

A palindrome reads the same forwards and backwards. The simplest way to check this is to reverse the string and compare it to the original. If they match, it's a palindrome. We iterate through the array and return the first string that passes this check.

Algorithm

Iterate through each word in the array.
For each word, create a reversed copy.
Compare the original word with its reversed version.
If they are equal, return that word immediately.
If no palindrome is found after checking all words, return an empty string.

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for w in words:
            if w == w[::-1]:
                return w
        return ""

public class Solution {
    public String firstPalindrome(String[] words) {
        for (String w : words) {
            if (w.equals(new StringBuilder(w).reverse().toString())) {
                return w;
            }
        }
        return "";
    }
}

class Solution {
public:
    string firstPalindrome(vector<string>& words) {
        for (const string& w : words) {
            string rev = w;
            reverse(rev.begin(), rev.end());
            if (w == rev) {
                return w;
            }
        }
        return "";
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @return {string}
     */
    firstPalindrome(words) {
        for (let w of words) {
            if (w === w.split('').reverse().join('')) {
                return w;
            }
        }
        return '';
    }
}

public class Solution {
    public string FirstPalindrome(string[] words) {
        foreach (string w in words) {
            char[] arr = w.ToCharArray();
            Array.Reverse(arr);
            if (w == new string(arr)) {
                return w;
            }
        }
        return "";
    }
}

func firstPalindrome(words []string) string {
    for _, w := range words {
        if isPalindrome(w) {
            return w
        }
    }
    return ""
}

func isPalindrome(s string) bool {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return s == string(runes)
}

class Solution {
    fun firstPalindrome(words: Array<String>): String {
        for (w in words) {
            if (w == w.reversed()) {
                return w
            }
        }
        return ""
    }
}

class Solution {
    func firstPalindrome(_ words: [String]) -> String {
        for w in words {
            if w == String(w.reversed()) {
                return w
            }
        }
        return ""
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(m)$

Where $n$ is the size of the string array $words$ and $m$ is the average length of a word in the array.

2. Two Pointers

Intuition

Instead of creating a reversed copy (which uses extra space), we can check if a string is a palindrome in place using two pointers. One pointer starts at the beginning, the other at the end. If all corresponding characters match as the pointers move toward each other, the string is a palindrome. This avoids the extra memory needed to store the reversed string.

Algorithm

Iterate through each word in the array.
For each word, use two pointers: l at the start and r at the end.
While the characters at l and r are equal:
- If l >= r, the word is a palindrome; return it.
- Move l forward and r backward.
If the characters differ, move to the next word.
If no palindrome is found, return an empty string.

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for w in words:
            l, r = 0, len(w) - 1
            while w[l] == w[r]:
                if l >= r:
                    return w
                l, r = l + 1, r - 1
        return ""

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

class Solution {
public:
    string firstPalindrome(vector<string>& words) {
        for (const string& w : words) {
            int l = 0, r = w.length() - 1;
            while (w[l] == w[r]) {
                if (l >= r) return w;
                l++;
                r--;
            }
        }
        return "";
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @return {string}
     */
    firstPalindrome(words) {
        for (let w of words) {
            let l = 0,
                r = w.length - 1;
            while (w.charAt(l) === w.charAt(r)) {
                if (l >= r) return w;
                l++;
                r--;
            }
        }
        return '';
    }
}

public class Solution {
    public string FirstPalindrome(string[] words) {
        foreach (string w in words) {
            int l = 0, r = w.Length - 1;
            while (w[l] == w[r]) {
                if (l >= r) return w;
                l++;
                r--;
            }
        }
        return "";
    }
}

func firstPalindrome(words []string) string {
    for _, w := range words {
        l, r := 0, len(w)-1
        for w[l] == w[r] {
            if l >= r {
                return w
            }
            l++
            r--
        }
    }
    return ""
}

class Solution {
    fun firstPalindrome(words: Array<String>): String {
        for (w in words) {
            var l = 0
            var r = w.length - 1
            while (w[l] == w[r]) {
                if (l >= r) return w
                l++
                r--
            }
        }
        return ""
    }
}

class Solution {
    func firstPalindrome(_ words: [String]) -> String {
        for w in words {
            let chars = Array(w)
            var l = 0
            var r = chars.count - 1
            while chars[l] == chars[r] {
                if l >= r {
                    return w
                }
                l += 1
                r -= 1
            }
        }
        return ""
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(1)$ extra space.

Where $n$ is the size of the string array $words$ and $m$ is the average length of a word in the array.

Common Pitfalls

Forgetting to Return an Empty String

A common mistake is forgetting to handle the case where no palindrome exists in the array. The problem requires returning an empty string "" when no palindromic string is found, not null or throwing an error. Always ensure your function has a default return statement after the loop completes.

Continuing Search After Finding the First Palindrome

Since the problem asks for the first palindromic string, you should return immediately upon finding one. A pitfall is iterating through the entire array and collecting all palindromes, then returning the first. This wastes time and misses the point of early termination, which is key to optimal performance.