Luffy asks "IsPalin" ?

Luffy with his crew is on the way to Dressrosa, where he will be fighting one of the warlords of the sea Doflamingo. But now he is getting bored and wants do a fun activity. He is very much obsessed with palindromes. Given a string S of lower case English alphabet of length N and two Integers L and R he wants to know whether all the letters of the substring from index L to R (L and R included) can be rearranged to form a palindrome or not. He wants to know this for Q values of L and R and needs your help in finding the answer.

A palindrome is a string of characters which when reversed reads same as the original String.

Example:

Input: n = 5, q = 5, s = "abcec", queries = {{1, 2}, {2, 5}, {3, 5}, {1, 5}, {1, 4}}

Output:

NO NO YES NO NO

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

void luffyAsksIsPalin(int nint qstring s,
                      vector<vector<int>> &queries)
{
    int a[n + 1][26] = {{0}};
    for (int i = 0i < ni++)
    {
        int c = s[i] - 'a';
        for (int j = 0j < 26j++)
            if (j == c)
                a[i + 1][j] = a[i][j] + 1;
            else
                a[i + 1][j] = a[i][j];
    }

    int cntfb[26];
    for (int i = 0i < qi++)
    {
        int l = queries[i][0]r = queries[i][1];
        b[26] = {0};
        cnt = 0f = 0;
        for (int j = 0j < 26j++)
        {
            b[j] = a[r][j] - a[l - 1][j];
            if (b[j] % 2)
                cnt++;
            if (cnt >= 2)
            {
                f = 1;
                break;
            }
        }
        if (f > 0)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

int main()
{

    int n = 5q = 5;
    string s = "abcec";

    vector<vector<int>> queries = {{12},
                                   {25},
                                   {35},
                                   {15},
                                   {14}};
    luffyAsksIsPalin(nqsqueries);

    return 0;
}


No comments:

Post a Comment