LeetCode 2108 - Find First Palindromic String in the Array

Difficulty: 🟢 Easy
Topics: Array, Two Pointers, String

Solution

Problem Understanding

The problem asks us to examine an array of strings, words, and identify the first string that is a palindrome. A palindrome is a string that reads the same forward and backward. In other words, the first character matches the last, the second matches the second-to-last, and so on. If no string in the array is a palindrome, the function should return an empty string "".

The input consists of an array of strings, where each string has at least one character and at most 100 characters, and the array contains between 1 and 100 strings. Each string contains only lowercase English letters. These constraints ensure that the input size is manageable and that string comparisons are straightforward, without worrying about upper/lowercase or non-alphabetic characters.

Important edge cases include arrays where no string is palindromic, arrays where the first string itself is a palindrome, and arrays where the palindrome occurs at the very end. The problem guarantees at least one string in the array, so we do not need to handle an empty array input.

Approaches

Brute Force Approach

The brute-force approach is straightforward: iterate through each string in the array and check if it is a palindrome. To check a string, compare its characters from the start and end moving toward the center. If all corresponding characters match, the string is palindromic. Once we find the first palindromic string, we return it. If no string matches, we return an empty string. This approach is simple and works correctly because it checks each string thoroughly, but the repeated character comparisons could be costly for longer strings, although within the problem constraints it is acceptable.

Optimal Approach

The optimal approach is essentially the same as brute force in this case because the input size is small. The key insight is that checking each string sequentially is efficient, and we can immediately return once we find a palindrome. There is no need for additional data structures or preprocessing because the operation is already linear in terms of the number of strings and the length of each string.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Iterate each string and check palindrome by comparing characters
Optimal	O(n * m)	O(1)	Same as brute force, but early exit as soon as a palindrome is found

n = number of strings, m = maximum string length

Algorithm Walkthrough

Iterate through each string word in the input array words.
For each word, check if it is a palindrome. Initialize two pointers, left at the start and right at the end of the string.
Compare the characters at left and right. If they match, move left forward and right backward.
If any characters do not match, the string is not a palindrome. Continue to the next string.
If all character comparisons match (i.e., left >= right), return this string immediately.
If no palindrome is found after checking all strings, return an empty string "".

Why it works: By comparing characters symmetrically from the ends toward the center, we guarantee that we correctly identify palindromes. Returning immediately upon the first successful check ensures we get the first palindromic string in the array.

Python Solution

from typing import List

class Solution:
    def firstPalindrome(self, words: List[str]) -> str:
        for word in words:
            left, right = 0, len(word) - 1
            is_palindrome = True
            while left < right:
                if word[left] != word[right]:
                    is_palindrome = False
                    break
                left += 1
                right -= 1
            if is_palindrome:
                return word
        return ""

The Python implementation iterates through each string in words and uses two pointers to check for a palindrome. The loop breaks early if a mismatch occurs. As soon as a palindrome is found, it is returned. If no palindrome is found in the entire array, an empty string is returned.

Go Solution

func firstPalindrome(words []string) string {
    for _, word := range words {
        left, right := 0, len(word)-1
        isPalindrome := true
        for left < right {
            if word[left] != word[right] {
                isPalindrome = false
                break
            }
            left++
            right--
        }
        if isPalindrome {
            return word
        }
    }
    return ""
}

The Go solution follows the same logic as Python. We use a for loop with range iteration over the slice. The palindrome check uses two indices moving toward the center. Early exit occurs on mismatch, and the first palindrome found is returned immediately. If none is found, an empty string is returned.

Worked Examples

Example 1: ["abc","car","ada","racecar","cool"]

Step	word	left	right	Comparison	Result
1	"abc"	0	2	'a' vs 'c'	Not palindrome
2	"car"	0	2	'c' vs 'r'	Not palindrome
3	"ada"	0	2	'a' vs 'a'	Match
		1	1	Stop	Palindrome found, return "ada"

Example 2: ["notapalindrome","racecar"]

Step	word	left	right	Comparison	Result
1	"notapalindrome"	0	14	'n' vs 'e'	Not palindrome
2	"racecar"	0	6	'r' vs 'r'	Match
		1	5	'a' vs 'a'	Match
		2	4	'c' vs 'c'	Match
		3	3	Stop	Palindrome found, return "racecar"

Example 3: ["def","ghi"]

Step	word	left	right	Comparison	Result
1	"def"	0	2	'd' vs 'f'	Not palindrome
2	"ghi"	0	2	'g' vs 'i'	Not palindrome
					No palindrome found, return ""

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * m)	Each of the n strings may require up to m comparisons to check for palindrome.
Space	O(1)	No additional space beyond loop variables is used.

The algorithm is efficient for the problem constraints since n ≤ 100 and m ≤ 100. Each string is checked at most once, and early exit further reduces unnecessary checks.

Test Cases

# Provided examples
assert Solution().firstPalindrome(["abc","car","ada","racecar","cool"]) == "ada"  # first palindrome is "ada"
assert Solution().firstPalindrome(["notapalindrome","racecar"]) == "racecar"      # first palindrome is at end
assert Solution().firstPalindrome(["def","ghi"]) == ""                             # no palindrome

# Boundary values
assert Solution().firstPalindrome(["a"]) == "a"                                     # single character is palindrome
assert Solution().firstPalindrome(["aa","bb","cc"]) == "aa"                          # first of all palindromes
assert Solution().firstPalindrome(["ab","ba","cc"]) == "cc"                          # last string palindrome

# Stress cases
assert Solution().firstPalindrome(["abcd"]*100) == ""                                 # all non-palindromes
assert Solution().firstPalindrome(["x"*100]) == "x"*100                                # max length palindrome

Test	Why
["abc","car","ada","racecar","cool"]	Standard input with first palindrome in the middle
["notapalindrome","racecar"]	First palindrome at the end
["def","ghi"]	No palindromes present
["a"]	Single character string
["aa","bb","cc"]	Multiple palindromes, first should be returned
["ab","ba","cc"]	Palindrome only at end
["abcd"]*100	Stress test with non-palindromes
["x"*100]	Stress test with maximum length palindrome

Edge Cases

Single character strings: A string with one character is always a palindrome. This is an edge case because a naive two-pointer implementation must handle left == right without assuming at least two characters. Our solution correctly identifies single-character strings as palindromes.
Maximum length strings: Strings of length 100 require up to 50 character comparisons. The implementation handles this without overflow or indexing errors because left and right are always within bounds.
No palindromes: Arrays where none of the strings are palindromes require the function to return an empty string. Our solution correctly iterates through all strings and only returns a string when it passes the palindrome check, otherwise returning `