Find First Palindromic String in the Array

Find First Palindromic String in the Array - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: words = ["abc","car","ada","racecar","cool"]

› Output: "ada"

💡 Note: The first palindromic string is "ada". Note that "racecar" is also palindromic but comes after "ada".

Example 2 — No Palindrome

$ Input: words = ["notlob","world"]

› Output: ""

💡 Note: None of the strings are palindromic, so return empty string.

Example 3 — Single Character

$ Input: words = ["def","ghi","a"]

› Output: "a"

💡 Note: Single character strings are palindromes. "a" is the first palindromic string.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of strings to check

Check Each String

Test palindrome property in order

Return First Match

Return first palindromic string found

Key Takeaway

🎯 Key Insight: Check strings sequentially and return the first one that reads the same forwards and backwards

Asked in

a Amazon 35 M Microsoft 28

The key insight is to check each string for palindrome property using two pointers. Best approach uses two pointers from ends moving inward for efficient palindrome verification. Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - String Reversal	O(n×m)	O(m)	Check each string by comparing with its reverse
Two Pointers Palindrome Check	O(n×m)	O(1)	Use two pointers from ends moving inward to check palindrome

Brute Force - String Reversal — Algorithm Steps

Iterate through each string in words
For each string, create reversed version
Compare original with reversed
Return first match or empty string

Visualization

Tap to expand

Step-by-Step Walkthrough

Check First Word

Compare 'abc' with 'cba' - not equal

Check Second Word

Compare 'car' with 'rac' - not equal

Check Third Word

Compare 'ada' with 'ada' - equal! Return 'ada'

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPalindrome(char* word) {
    int len = strlen(word);
    char reversed[len + 1];
    
    for (int i = 0; i < len; i++) {
        reversed[i] = word[len - 1 - i];
    }
    reversed[len] = '\0';
    
    return strcmp(word, reversed) == 0;
}

char* solution(char words[][100], int n) {
    static char result[100];
    
    for (int i = 0; i < n; i++) {
        if (isPalindrome(words[i])) {
            strcpy(result, words[i]);
            return result;
        }
    }
    
    strcpy(result, "");
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char words[100][100];
    int count = 0;
    
    char* token = strtok(line, "[],\"\n");
    while (token != NULL) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            strcpy(words[count], token);
            count++;
        }
        token = strtok(NULL, "[],\"\n");
    }
    
    char* result = solution(words, count);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Visit each of n strings, reverse operation takes O(m) time where m is average string length

✓ Linear Growth

Space Complexity

O(m)

Create reversed string of length m for each comparison

✓ Linear Space

24.3K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - String Reversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler