Alice and Strings

3.4

62 votes
Algorithms, Easy, String Manipulation
Problem

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.

Input format

First line: String A 

Next line: String B

Output format

For each test case, print YES if string A can be converted to string B , otherwise print NO.

Constraints

1len(A)10000001len(B)1000000

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The string abaca can be converted to bcbda in one move and to cdbda in the next move.

Editor Image

?