algoadvance

Given an array of strings words, find the first palindromic string in the array. A string is considered palindromic if it reads the same forward and backward. If there is no such string, return an empty string "".

Clarifying Questions

1. Case Sensitivity: Should the palindrome check be case-sensitive?
   • Yes, by default, the problem is case-sensitive unless specified otherwise.
2. Input Constraints: What are the constraints on the length of the array and the strings within it?
   • It is typically reasonable to assume that the array length and each string length will fit within typical problem constraints (e.g., thousands of elements and lengths).

Code

def first_palindromic_string(words):
    for word in words:
        if word == word[::-1]:  # Check if word is a palindrome by comparing it to its reverse
            return word
    return ""

# Example usage:
# words = ["abc", "car", "ada", "racecar", "cool"]
# print(first_palindromic_string(words))  # Output: "ada"

Strategy

1. Iteration through the Array: Loop through each word in the given list of strings.
2. Check for Palindrome: For each word, check if the word is a palindrome by comparing the word with its reverse (word[::-1]).
3. Return the First Palindrome: Once a palindrome is found, immediately return it.
4. Handle No Palindrome Case: If no palindrome is found after checking all words, return an empty string.

Time Complexity

• Time Complexity: The time complexity is ( O(n \cdot m) ), where ( n ) is the number of words in the list, and ( m ) is the average length of the words. This is because for each of the ( n ) words, checking if it is a palindrome involves comparing ( m ) characters.
• Space Complexity: The space complexity is ( O(1) ) for storing intermediary variables, though some additional space is used to store the reversed string, which also scales with the length of the words.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?