Compare Strings

You have been given two strings, A and B (of length N each) and Q queries.

The strings contain only 0s and/or 1s.

For every query, you are given an index i. You have to update the value at index i to 1 in string B and check if B is lexicographically equal to or larger than A or not.
If yes, then print "YES" and if not, print "NO" (without quotes).

Example:

Input:  n = 5, q = 5, s1 = "11111", s2 = "00010", queries = {1, 2, 3, 4, 5}

Output:

NO NO NO NO YES

Approach:

C++

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

void comapreStrings(int nstring s1,
                    string s2int q,
                    vector<int&queries)
{

    int i = 0;
    for (int j = 0j < qj++)
    {
        int pos = queries[j];

        pos--;
        s2[pos] = '1';

        do
        {
            if (s1[i] == '1' && s2[i] == '0')
                break;
            i++;
        } while (i < n && pos == i);
        if (i == n)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}
int main()
{

    int n = 5q = 5;
    string s1 = "11111"s2 = "00010";

    vector<intqueries = {12345};
    comapreStrings(ns1s2qqueries);

    return 0;
}


No comments:

Post a Comment