Jobs

Interviews

Discussions

Find First Palindromic String in the Array

#675 Most AskedEasy

Find First Palindromic String in the Array #675 Most Asked

Easy

Bloomberg LP

7 views

Topics:

ArraysStringsTwo Pointers

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.

Try coding it in LeetCode

Find First Palindromic String in the Array

#675 Most AskedEasy

Find First Palindromic String in the Array #675 Most Asked

Easy

Bloomberg LP

7 views

Topics:

ArraysStringsTwo Pointers

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if there are no palindromic strings in the input array?
Can the input array contain null or empty strings, and if so, how should I handle them?
Are the strings in the array case-sensitive? Should I treat 'Racecar' and 'racecar' as palindromes?
What is the maximum length of a string within the array?
If there are multiple palindromic strings, should I return the *first* one encountered in the array or is there another selection criterion?

Brute Force Solution

Approach

The brute force method involves checking each word one by one to see if it reads the same forwards and backward. As soon as we discover a word that is a palindrome, we can stop and return it. We continue the search until we either find a palindrome or run out of words.

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the word is a palindrome. This means seeing if it's the same when read from left to right and right to left.
If the word is a palindrome, you've found the answer! Stop and return this word.
If the word is not a palindrome, move on to the next word in the list.
Repeat steps 2-4 for each word in the list until you find a palindrome.
If you reach the end of the list and haven't found any palindromes, it means there are no palindromes in the list. In this case, return an indication that no palindrome was found.

Code Implementation

def find_first_palindrome(words):
    for word in words:
        # Iterate through each word in the input list
        is_palindrome = True

        left_index = 0
        right_index = len(word) - 1

        while left_index < right_index:
            # Compare characters from both ends until meet
            if word[left_index] != word[right_index]:
                is_palindrome = False
                break
            left_index += 1
            right_index -= 1

        # If the word is a palindrome, return it
        if is_palindrome:
            return word

    # No palindrome was found so return empty string
    return ""

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the n words in the input array. For each word, it checks if it's a palindrome by comparing characters from the beginning and end towards the middle. In the worst case, checking a single word of length m requires comparing m/2 character pairs, which is O(m). Since we perform this check for each of the n words, the overall time complexity is O(n*m), where n is the number of words and m is the average length of the words.

Space Complexity

O(1) – The provided algorithm iterates through the input array and checks each word for being a palindrome. The palindrome check itself can be done in-place, or by using a constant amount of extra memory to compare characters. No data structures that scale with the size of the input array are used, meaning the extra memory used is independent of the input array size N (where N is the number of words in the input array). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to find the first palindromic string is to check each word one by one. As soon as we find a word that's a palindrome, we can stop searching and return it immediately. This avoids unnecessary checks.

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the word reads the same forwards and backward. If it does, this is our answer, so we can stop.
If the word is not a palindrome, move on to the next word in the list.
Repeat the process of checking if the current word is a palindrome.
Keep going until you find a palindrome or run out of words.
If you find a palindrome, return it. If you run out of words without finding one, it means there are no palindromes in the list.

Code Implementation

def find_first_palindrome(words_list):
    for word in words_list:
        # Check if the current word is a palindrome.
        if word == word[::-1]:

            # Return the word immediately since it's a palindrome.
            return word

    # If no palindrome is found, return an empty string.
    return ""

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the n strings in the input array. For each string, it checks if the string is a palindrome. Checking if a string is a palindrome requires iterating through the string of length m, which takes O(m) time in the worst case. Therefore, the overall time complexity is O(n*m), where n is the number of strings in the input array, and m is the maximum length of any string in the array. Once the first palindrome is found, the algorithm terminates, but the worst-case scenario involves checking all strings.

Space Complexity

O(1) – The provided solution iterates through the array of strings and checks each string to see if it is a palindrome. The only extra space required is for potentially storing the original string, or storing indices for comparison when checking for a palindrome. The space required for these operations does not depend on the number of strings in the input array (N) or the lengths of the strings, and remains constant. Thus, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null input array	Return null or throw an IllegalArgumentException, depending on the specifications and language conventions.
Empty input array	Return an empty string because no palindromic string can exist.
Array containing an empty string	An empty string is considered a palindrome; the algorithm should return it if it's the first one found.
Array containing a single string	Check if the single string is a palindrome and return it; otherwise, return an empty string.
Array with very long strings	The palindrome check should still function correctly but might impact performance; consider optimizing for long string palindrome checks if necessary.
Array with no palindromic strings	The algorithm should return an empty string after iterating through the entire array without finding a palindrome.
Array with multiple palindromic strings	The algorithm should return the first palindromic string encountered in the array, as per the problem statement.
Strings with mixed case or non-alphanumeric characters.	The palindrome check logic should normalize the strings (e.g., convert to lowercase and remove non-alphanumeric characters) before comparison if this is desired behavior.

Null input array

How to Handle:

Return null or throw an IllegalArgumentException, depending on the specifications and language conventions.

Empty input array

How to Handle:

Return an empty string because no palindromic string can exist.

Array containing an empty string

How to Handle:

An empty string is considered a palindrome; the algorithm should return it if it's the first one found.

Array containing a single string

How to Handle:

Check if the single string is a palindrome and return it; otherwise, return an empty string.

Array with very long strings

How to Handle:

The palindrome check should still function correctly but might impact performance; consider optimizing for long string palindrome checks if necessary.

Array with no palindromic strings

How to Handle:

The algorithm should return an empty string after iterating through the entire array without finding a palindrome.

Array with multiple palindromic strings

How to Handle:

The algorithm should return the first palindromic string encountered in the array, as per the problem statement.

Strings with mixed case or non-alphanumeric characters.

How to Handle:

The palindrome check logic should normalize the strings (e.g., convert to lowercase and remove non-alphanumeric characters) before comparison if this is desired behavior.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if there are no palindromic strings in the input array?
Can the input array contain null or empty strings, and if so, how should I handle them?
Are the strings in the array case-sensitive? Should I treat 'Racecar' and 'racecar' as palindromes?
What is the maximum length of a string within the array?
If there are multiple palindromic strings, should I return the *first* one encountered in the array or is there another selection criterion?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the word is a palindrome. This means seeing if it's the same when read from left to right and right to left.
If the word is a palindrome, you've found the answer! Stop and return this word.
If the word is not a palindrome, move on to the next word in the list.
Repeat steps 2-4 for each word in the list until you find a palindrome.
If you reach the end of the list and haven't found any palindromes, it means there are no palindromes in the list. In this case, return an indication that no palindrome was found.

Code Implementation

def find_first_palindrome(words):
    for word in words:
        # Iterate through each word in the input list
        is_palindrome = True

        left_index = 0
        right_index = len(word) - 1

        while left_index < right_index:
            # Compare characters from both ends until meet
            if word[left_index] != word[right_index]:
                is_palindrome = False
                break
            left_index += 1
            right_index -= 1

        # If the word is a palindrome, return it
        if is_palindrome:
            return word

    # No palindrome was found so return empty string
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first word from the list.
Check if the word reads the same forwards and backward. If it does, this is our answer, so we can stop.
If the word is not a palindrome, move on to the next word in the list.
Repeat the process of checking if the current word is a palindrome.
Keep going until you find a palindrome or run out of words.
If you find a palindrome, return it. If you run out of words without finding one, it means there are no palindromes in the list.

Code Implementation

def find_first_palindrome(words_list):
    for word in words_list:
        # Check if the current word is a palindrome.
        if word == word[::-1]:

            # Return the word immediately since it's a palindrome.
            return word

    # If no palindrome is found, return an empty string.
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Return null or throw an IllegalArgumentException, depending on the specifications and language conventions.
Empty input array	Return an empty string because no palindromic string can exist.
Array containing an empty string	An empty string is considered a palindrome; the algorithm should return it if it's the first one found.
Array containing a single string	Check if the single string is a palindrome and return it; otherwise, return an empty string.
Array with very long strings	The palindrome check should still function correctly but might impact performance; consider optimizing for long string palindrome checks if necessary.
Array with no palindromic strings	The algorithm should return an empty string after iterating through the entire array without finding a palindrome.
Array with multiple palindromic strings	The algorithm should return the first palindromic string encountered in the array, as per the problem statement.
Strings with mixed case or non-alphanumeric characters.	The palindrome check logic should normalize the strings (e.g., convert to lowercase and remove non-alphanumeric characters) before comparison if this is desired behavior.

Null input array

How to Handle:

Return null or throw an IllegalArgumentException, depending on the specifications and language conventions.

Empty input array

How to Handle:

Return an empty string because no palindromic string can exist.

Array containing an empty string

How to Handle:

An empty string is considered a palindrome; the algorithm should return it if it's the first one found.

Array containing a single string

How to Handle:

Check if the single string is a palindrome and return it; otherwise, return an empty string.

Array with very long strings

How to Handle:

The palindrome check should still function correctly but might impact performance; consider optimizing for long string palindrome checks if necessary.

Array with no palindromic strings

How to Handle:

The algorithm should return an empty string after iterating through the entire array without finding a palindrome.

Array with multiple palindromic strings

How to Handle:

The algorithm should return the first palindromic string encountered in the array, as per the problem statement.

Strings with mixed case or non-alphanumeric characters.

How to Handle:

The palindrome check logic should normalize the strings (e.g., convert to lowercase and remove non-alphanumeric characters) before comparison if this is desired behavior.

0/1037 Bloomberg LP questions completed

0/1037 completed