question 2 Solution
void solve()
{
int n;
cin>>n;
vector<string> newpass(n);
vector<string> old(n);
f(i,n)
cin>>newpass[i];
f(i,n)
cin>>old[i];
for(int i=0;i<n;i++)
{
string np=newpass[i];
string oldpass=old[i];
int sz1=np.size();
int sz2=oldpass.size();
int j=0;
int k=0;
while(j<sz1 && k<sz2)
{
char comp=np[j];
char next=comp;
if(comp=='z')
{
next='a';
}
else
next++;
if(comp==oldpass[k] || oldpass[k]==next)
k++;
j++;
}
if(k==sz2)
cout<<"YES"<<" ";
else
cout<<"NO"<<" ";
}
cout<<endl;
}
int32_t main()
{
solve();
}
It is too trivial, simply track number of '+' and '-' signs as you process each event and report the maximum amongst it
Proble in Brief
Determine if an old password can be a subsequence of a new password after applying cyclic changes to a subset of indices in the new password.
Core Idea
The essence of the solution lies in the observation that we don't need to generate all possible combinations of cyclic changes in the new password. Instead, we can use a two-pointer approach to simulate this. By comparing characters of the old password with either the original or the cyclically changed character of the new password, we can determine if the old password can be a subsequence of the new password with some cyclic changes.
Approach:
C++ Code:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
char nextCyclicChar(char ch) {
if (ch == 'z') return 'a';
return ch + 1;
}
bool isPossibleSubsequence(const string& oldPass, const string& newPass) {
int i = 0, j = 0;
while (i < oldPass.size() && j < newPass.size()) {
if (oldPass[i] == newPass[j] || oldPass[i] == nextCyclicChar(newPass[j])) {
i++;
}
j++;
}
return i == oldPass.size();
}
void arePasswordsSimilar(const vector<string>& oldPasswords, const vector<string>& newPasswords) {
for (int k = 0; k < oldPasswords.size(); k++) {
if (isPossibleSubsequence(oldPasswords[k], newPasswords[k])) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
int main() {
vector<string> oldPasswords = {"abdbc", "accdb", "abc"};
vector<string> newPasswords = {"baacbab", "ach", "abc"};
arePasswordsSimilar(oldPasswords, newPasswords);
return 0;
}
is it correct ,100%?
Yes Suryansh's solution looks correct indeed. I have added my code + explanation to make it super clear.