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 "" and if not, print "" (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 n, string s1,string s2, int q,vector<int> &queries){int i = 0;for (int j = 0; j < q; j++){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";elsecout << "NO\n";}}int main(){int n = 5, q = 5;string s1 = "11111", s2 = "00010";vector<int> queries = {1, 2, 3, 4, 5};comapreStrings(n, s1, s2, q, queries);return 0;}
No comments:
Post a Comment