<p>Given an array of strings <code>words</code>, return <em>the first <strong>palindromic</strong> string in the array</em>. If there is no such string, return <em>an <strong>empty string</strong> </em><code>&quot;&quot;</code>.</p>

<p>A string is <strong>palindromic</strong> if it reads the same forward and backward.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;abc&quot;,&quot;car&quot;,&quot;ada&quot;,&quot;racecar&quot;,&quot;cool&quot;]
<strong>Output:</strong> &quot;ada&quot;
<strong>Explanation:</strong> The first string that is palindromic is &quot;ada&quot;.
Note that &quot;racecar&quot; is also palindromic, but it is not the first.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;notapalindrome&quot;,&quot;racecar&quot;]
<strong>Output:</strong> &quot;racecar&quot;
<strong>Explanation:</strong> The first and only string that is palindromic is &quot;racecar&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;def&quot;,&quot;ghi&quot;]
<strong>Output:</strong> &quot;&quot;
<strong>Explanation:</strong> There are no palindromic strings, so the empty string is returned.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 100</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 100</code></li>
	<li><code>words[i]</code> consists only of lowercase English letters.</li>
</ul>

// clang-format off
static const auto io_sync_off = []() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return 0; }();
using ll = long long; using SS = stringstream;
using pii = pair<int, int>; using pis = pair<int, string>; using psi = pair<string, int>;
template<typename T> using V = vector<T>; template<typename T> using VV = V<V<T>>; template<typename T> using VVV = VV<V<T>>;
using vi = V<int>; using vvi = VV<int>; using vvvi = VVV<int>; using vb = V<bool>; using vvb = VV<bool>; using vs = V<string>; using vd = V<double>; using vli = V<list<int>>;
template<typename T> using US = unordered_set<T>; template<typename A, typename B> using UM = unordered_map<A, B>;
using si = set<int>; using usi = US<int>; using uss = US<string>;
using mii = map<int, int>; using umii = UM<int, int>; using umib = UM<int, bool>; using umsi = UM<string, int>;
using pqi = priority_queue<int, vi, greater<int>>; using pqri = priority_queue<int, vi>;
constexpr int BIG = 1e9; constexpr int MOD = 1e9 + 7; constexpr int MAX_INT = INT_MAX; constexpr bool fasle = false; constexpr bool ture = true;
#define _(t, k) get<(k)>(t)
#define _0(t) _((t), 0)
#define _1(t) _((t), 1)
#define _2(t) _((t), 2)
#define fi first
#define se second
#define pb push_back
#define F(i, a, b) for(int(i) = (a); (i) < (b); ++(i))
#define Fe(i, a, b) for(int(i) = (a); (i) <= (b); ++(i))
#define FR(i, a, b) for(int(i) = (a); (i) >= (b); --(i))
#define FRn(i, a, b) for(int(i) = (a); (i) > (b); --(i))
#define FE(a, v) for(auto &(a): (v)) // For each element in a container...
#define FEv(v, m) for(auto &[k, v]: (m)) // For each element in a map or unordered_map...
#define FEt(t, s) SS ss(s); for(string (t); ss >> (t);) // For each token in a string...
#define W(n) while((n)--)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v)) // Sort elements in ascending order.
#define SORTR(v) sort(ALL(v), greater()) // Sort elements in descending order.
#define SORTf(v, f) sort(ALL(v), (f)) // Sort elements based on a function. E.g. `SORTf(v, greater())`.
#define SORTfab(v, fab) sort(ALL(v), [&](auto &a, auto &b) { return (fab); }) // Sort elements based on an expression of any 2 elements `a` and `b`.
#define COUNT(v, k) count(ALL(v), (k)) // Count elements with value `k`.
#define COUNTfa(v, fa) count_if(ALL(v), [&](auto &a) { return (fa); }) // Count elements based on an expression of any elemnent `a`.
#define R(v) reverse(ALL(v)) // Reverse elements in a container.
#define sz(v) int((v).size())
#define szv(n, v) int(n) = sz(v)
#define szvv(m, n, vv) int(m) = sz(vv), (n) = (m) ? sz((vv)[0]) : 0
#define maxe(v) max_element(ALL(v))
#define mine(v) max_element(ALL(v))
#define maxv(v) *maxe(v) // Max element in a container.
#define minv(v) *mine(v) // Min element in a container.
#define maxvi(v) maxe(v) - (v).begin() // Index of max element in a container.
#define minvi(v) mine(v) - (v).begin() // Index of min element in a container.
#define IOTA(v) iota(ALL(v), 0) // Fill a container with 0, 1, 2, ...
#define SUM(v) accumulate(ALL(v), 0) // Sum of elements in a container.
#define SUMfa(v, fa) accumulate(ALL(v), 0, [](int s, int a) { return s + ((fa) ? a : 0); }) // Sum elements based on an expression of any element `a`.
template<typename T> vi HISTV(const T &v, int n, int b = 0, const function<bool(const typename T::value_type&)> &f = [](const typename T::value_type &a) { return true; }) { vi hist(n); FE(a, v) if(f(a)) hist[a - b]++; return hist; }
#define HISTVf(v, n, b, f) HISTV((v), (n), (b), (f))
#define HISTVfa(v, n, b, fa) HISTV((v), (n), (b), [](auto &a) { return (fa); })
template<typename T> UM<typename T::value_type, int> HISTM(const T &v, const function<bool(const typename T::value_type &)> &f = [](const typename T::value_type &a) { return true; }) { UM<typename T::value_type, int> um; FE(a, v) if(f(a)) um[a]++; return um; }
#define HISTMf(v, f) HISTM((v), (f))
#define HISTMfa(v, fa) HISTM((v), [](auto &a) { return (fa); })
template<typename T> V<typename T::mapped_type> MV(const T &m) { V<typename T::mapped_type> v(sz(m)); int i = 0; FEv(a, m) v[i++] = a; return v; }
template<typename T> V<pair<typename T::key_type, typename T::mapped_type>> MP(const T &m) { V<pair<typename T::key_type, typename T::mapped_type>> v(sz(m)); int i = 0; FE(p, m) v[i++] = p; return v; }
template<typename T> T Pop(queue<T> &q) { T r = q.front(); q.pop(); return r; } template<typename C> typename C::value_type Pop(C &c) { typename C::value_type r = c.top(); c.pop(); return r; }
template<typename A> VV<A> T(const VV<A> &vv) { szvv(X, Y, vv); VV<A> r(X, V<A>(Y)); for(int y = 0; y < Y; y++) for(int x = 0; x < X; x++) r[y][x] = vv[x][y]; return r; }
template<typename T> void P_(const T &t) { cout << t << " "; } template<typename T> void P_(const V<T> &v) { FE(k, v) cout << k << " "; cout << endl; } template<typename T> void P_(const VV<T> &vv) { FE(v, vv) { FE(k, v) cout << k << " "; cout << endl; } }
template<typename ...T> void P(const T& ...t) { (P_(t), ...); cout << endl; }
template<typename A, typename B> pair<A, B> operator+(const pair<A, B> &a, const pair<A, B> &b) { return {a.fi + b.fi, a.se + b.se}; } template<typename A, typename B> pair<A, B> &operator+=(pair<A, B> &a, const pair<A, B> &b) { a.fi += b.fi; a.se += b.se; return a; }
// clang-format on
class Solution {
public:

    bool isPalindrome(string s){
        int left = 0;
        int right = s.length()-1;

        while(left<right){
            if(s[left]!=s[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;

    }

    string firstPalindrome(vector<string>& words) {
        for(string s: words){
            if(isPalindrome(s)){
                return s;
            }
        }
        return "";
    }
};
30300