algoadvance

Leetcode 2108. Find First Palindromic String in the Array

Problem Statement

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.

Clarifying Questions

  1. What is the expected input size?
    • The array can have up to (10^5) strings and each string length can be up to 100 characters.
  2. What characters do the strings consist of?
    • The strings only consist of lowercase English letters.
  3. Should the function handle empty strings in the input array?
    • Yes, the function should handle empty strings, which are inherently palindromic.
  4. Is there any restriction on processing time?
    • Standard limits apply, typically aiming for (O(N \times M)), where (N) is the number of strings and (M) is the average length of the strings.

Strategy

  1. Check Each String for Palindrome:
    • Iterate over each string in the array.
    • For each string, check if it is a palindrome:
      • Use two-pointer technique to check if the string reads the same forwards and backwards:
        • Initialize two pointers, one at the start and one at the end of the string.
        • Move the start pointer forward and the end pointer backward, comparing the characters at each step.
        • If the characters at the two pointers are different, the string is not a palindrome.
        • If the pointers cross each other without finding different characters, the string is a palindrome.
  2. Return the first palindromic string found:
    • Once a palindromic string is found, return it immediately.
    • If no palindromic string is found by the end of the array, return an empty string "".

Code

#include <vector>
#include <string>

class Solution {
public:
    std::string firstPalindrome(std::vector<std::string>& words) {
        for (const auto& word : words) {
            if (isPalindrome(word)) {
                return word;
            }
        }
        return "";
    }
    
private:
    bool isPalindrome(const std::string& s) {
        int left = 0;
        int right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI