The question states: Two strings A and B comprising of lower case English letters are compatible if they are equal or can be made equal by following this step any number of times:
Select a prefix from the string A(possibly empty), and increase the alphabetical value of all the characters in the prefix by the same valid amount. For example, if the string is xyz and we select the prefix xy then we can convert it to yz by increasing the alphabetical value by 1. But if we select the prefix xyz then we cannot increase the alphabetical value. Your task is to determine if given strings A and B are compatible.
The logic here is that the difference of lower indices of the two string should never increase that of higher indices. That is what I did. And the two test cases are really long but not longer than what we can store in string type. That is why I have not provided it here.
#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
string s1;
string s2;
cin>>s1>>s2;
long long int count=0,max=0;
if(s2.length()!=s1.length())
{
cout<<"NO";
return 0;
}
for(int i=0;s1[i]!='\0';i++)
{
if(s1[i]==s2[i])
break;
else
count++;
}
for(int i=count-1;i>=0;i--)
{
if(s2[i]-s1[i]>=max && s2[i]-s1[i]>0 && s2[i]-s1[i]<26)
max= s2[i]-s1[i];
else
{
cout<<"NO";
return 0;
}
}
cout<<"YES";
return 0;
}
//The tester correct code is as follows:
#include<bits/stdc++.h>
using namespace std;
int main()
{
string a,b;
assert(cin>>a>>b);
assert(a.size()>=1 && a.size()<=1e6);
assert(b.size()>=1 && b.size()<=1e6);
bool f=1;
if(a.size()!=b.size())f=0;
else
{
int val=30;
for(int i=0;i<a.size();i++)
{
assert(a[i]>='a' && a[i]<='z');
assert(b[i]>='a' && b[i]<='z');
int temp=b[i]-a[i];
if(temp>val || temp<0){f=0;break;}
val=temp;
}
}
if(f)cout<<"YES\n";
else cout<<"NO\n";
return 0;
}
