Find First Palindromic String in the Array

Easy

#1920Time: O(N * K), where N is the number of strings in the `words` array and K is the maximum length of a string in the array. We iterate through N words, and for each word of length K, reversing and comparing takes O(K) time.Space: O(K), where K is the maximum length of a string. This is because we need to create a new string (or `StringBuilder`) of length K to store the reversed version of the string for comparison.

Patterns

Two Pointers

Data structures

Array String

Prompt

Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: words = ["abc","car","ada","racecar","cool"]
Output: "ada"
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first.

Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".

Example 3:

Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each string in the input array. For each string, it checks if it's a palindrome by creating a reversed copy of the string and comparing it with the original. The first string that matches its reversed version is returned.

Algorithm

Iterate through each word in the words array.
For each word, call a helper function isPalindrome(word).
In isPalindrome(word): a. Create a new StringBuilder object from the word. b. Reverse the StringBuilder. c. Convert the reversed StringBuilder back to a String. d. Compare the original word with the reversed string. Return true if they are equal, false otherwise.
If isPalindrome(word) returns true, return the current word.
If the loop completes without finding any palindromes, return an empty string "".

Walkthrough

The main idea is to traverse the words array from the beginning. For each word, we create a helper function, isPalindrome, to determine if it's a palindrome. Inside isPalindrome, we use a StringBuilder to create a reversed version of the input string. We then convert the StringBuilder back to a String and compare it with the original string using the .equals() method. If isPalindrome returns true, we have found our first palindromic string, and we can immediately return it. If the loop finishes without finding any palindromes, it means no such string exists in the array, so we return an empty string "".

1class Solution {2    public String firstPalindrome(String[] words) {3        for (String word : words) {4            if (isPalindrome(word)) {5                return word;6            }7        }8        return "";9    }10 11    private boolean isPalindrome(String s) {12        String reversed_s = new StringBuilder(s).reverse().toString();13        return s.equals(reversed_s);14    }15}

Complexity

Time

O(N * K), where N is the number of strings in the `words` array and K is the maximum length of a string in the array. We iterate through N words, and for each word of length K, reversing and comparing takes O(K) time.

Space

O(K), where K is the maximum length of a string. This is because we need to create a new string (or `StringBuilder`) of length K to store the reversed version of the string for comparison.

Trade-offs

Pros

Simple to understand and implement.
Leverages built-in language features for string manipulation, leading to concise code.

Cons

Less efficient in terms of space, as it requires extra memory to store the reversed string.
Can be slightly slower in practice due to the overhead of creating new string objects.

This is a more optimized approach. It also iterates through each string in the array, but the palindrome check is performed more efficiently using a two-pointer technique. This avoids creating a new string, thus saving space.

Algorithm

Iterate through each word in the words array.
For each word, call a helper function isPalindrome(word).
In isPalindrome(word): a. Initialize two pointers: left = 0 and right = word.length() - 1. b. Loop while left < right. c. Inside the loop, check if word.charAt(left) is not equal to word.charAt(right). If they are different, return false. d. Increment left and decrement right. e. If the loop completes, it means all characters matched, so return true.
If isPalindrome(word) returns true, return the current word.
If the loop completes, return an empty string "".

Walkthrough

Similar to the first approach, we iterate through the words array. The key difference is in the isPalindrome helper function. This function uses two pointers, left starting at the beginning of the string (index 0) and right starting at the end (index length - 1). The pointers move towards each other. In each step, we compare the characters at the left and right pointers. If at any point the characters do not match, we know it's not a palindrome, and the function returns false. If the pointers cross or meet (left >= right) without finding any mismatches, it means the string is a palindrome, and the function returns true. The main function returns the first word for which isPalindrome returns true. If the loop finishes, it returns an empty string.

1class Solution {2    public String firstPalindrome(String[] words) {3        for (String word : words) {4            if (isPalindrome(word)) {5                return word;6            }7        }8        return "";9    }10 11    private boolean isPalindrome(String s) {12        int left = 0;13        int right = s.length() - 1;14        while (left < right) {15            if (s.charAt(left) != s.charAt(right)) {16                return false;17            }18            left++;19            right--;20        }21        return true;22    }23}

Complexity

Time

O(N * K), where N is the number of strings and K is the maximum length of a string. We iterate through N words. For each word of length K, the two-pointer check takes O(K/2) which is O(K) time.

Space

O(1). The two-pointer check is done in-place and uses only a constant amount of extra space for the pointers, regardless of the input string's length.

Trade-offs

Pros

Highly efficient in terms of space complexity (O(1)).
Generally faster in practice than the reversal method because it avoids object creation and can terminate early as soon as a mismatch is found.

Cons

The implementation is slightly more manual compared to using a built-in reverse function.

Solutions

Solution

1class Solution {2public3  String firstPalindrome(String[] words) {4    for (var w : words) {5      boolean ok = true;6      for (int i = 0, j = w.length() - 1; i < j && ok; ++i, --j) {7        if (w.charAt(i) != w.charAt(j)) {8          ok = false;9        }10      }11      if (ok) {12        return w;13      }14    }15    return "";16  }17}

1class Solution {2public:3  string firstPalindrome(vector<string> &words) {4    for (auto &w : words) {5      bool ok = true;6      for (int i = 0, j = w.size() - 1; i < j; ++i, --j) {7        if (w[i] != w[j]) {8          ok = false;9        }10      }11      if (ok) {12        return w;13      }14    }15    return "";16  }17};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem