In this HackerEarth Alice and Strings problem solution 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.


HackerEarth Alice and Strings problem solution


HackerEarth Alice and Strings problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mx=1e6;
int main()
{
string a,b;cin>>a>>b;
assert((a.size()<=mx)&&(b.size()<=mx));
if(a.size()!=b.size()){cout<<"NO"<<endl;return 0;}
int n=a.size();int diff[n]={0};
for(int i=0;i<n;i++)diff[i]=b[i]-a[i];
bool p=(diff[n-1]>=0);
for(int i=0;i<n-1;i++)
p&=(diff[i]>=0&&diff[i]>=diff[i+1]);
cout<<(p?"YES":"NO")<<endl;
}

Second solution

#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;
}