Scale Engineer

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
ArrayString

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

  1. Iterate through each word in the words array.
  2. For each word, call a helper function isPalindrome(word).
  3. 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.
  4. If isPalindrome(word) returns true, return the current word.
  5. 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 "".

class Solution {    public String firstPalindrome(String[] words) {        for (String word : words) {            if (isPalindrome(word)) {                return word;            }        }        return "";    }     private boolean isPalindrome(String s) {        String reversed_s = new StringBuilder(s).reverse().toString();        return s.equals(reversed_s);    }}

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.

Solutions

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

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 →

Next problem