Basics of String Manipulation:

A string is a sequence of characters. In other words, a string is an array of character data type. An instance of a string is called a string literal. For instance in C++: string s = "HackerEarth"; $s$ is a string literal.
Let us discuss a small problem on strings

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.

Approach:

• First try to find length of strings .If lengths are not equal then it is not possible to convert A to B
• Secondly,Find no of conversions required for prefix if the no of conversions of prefix is less than the remaining part of string,then also it is not possible to convert A to B.
Implementation of above approach with Code

#include<iostream>
#include<string.h>
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2;
int l1=s1.length();
int l2=s2.length();
if(l1!=l2){
//If lengths are not equal obviously A cant be converted to B
cout<<"NO"<<endl;
}
else{
int max=9999;
int diff;
int bool1=true;
for(int i=0;i<l1;i++){
diff=s2[i]-s1[i];
if(diff<=max){
//No of conversions required for the prefix should be greater
max=diff;
}
else{
//If no of conversions required for prefix is less then it is not possible to convert
cout<<"NO"<<endl;
bool1=false;
break;
}
}
if(bool1){
cout<<"YES"<<endl;
}
}
}
-------------------------------------------------
Input:
abaca
cdbda

Output:
YES

More Articles of M Mounika:

Name Views Likes
C++ Segmented Sieve (Print Primes In a Range) 162 0
C++ Sieve Of Erastosthenes 135 0
C++ Gold Mine Problem 294 0
C++ Merge K Sorted Arrays 116 0
C++ K Centers Problem 239 0
C++ Find Nth Catalan Number 311 0
C++ Inplace Rotate square matrix by 90 degrees 285 0
C++ Find Non Repeating Elements in Array 86 0
C++ Merge Two Binary Trees 120 0
C++ Sum of Numbers From Root To Leaf Paths 88 0
C++ Meta Strings 91 0
C++ Flood Fill Algorithm 402 0
C++ smallest substring with maximum distinct characters 199 0
C++ Smallest window with all characters in string 93 0
C++ Minimum Removal of Characters from string to make its permutation as palindrome 86 0
C++ Minimum characters added at front of string in palindrome conversion 69 0
C++ Number of Bracket Reversals needed to make expression Balanced 72 0
C++ String to Palindrome with Append Function 83 0
C++ WildCard pattern matching 75 0
C++ Anagram substring Search 72 0
C++ Manachars Algorithm 74 0
C++ Search String in Grid 83 0
C++ String Matching(Z Algorithm) 67 0
C++ String Matching(Naive Algorithm) 113 0
C++ String Matching(KMP Algorithm) 140 0
C++ Remove Duplicates From String 110 0
C++ Basics of String Manipulation 85 1
C++ Disjoint Data Structure Cycle Detection 86 0
C++ Problem On Disjoint Data Structures 94 0
C++ Disjoint Data Structures Part3 78 0
Disjoint Data Structures Part2 90 0
Disjoint Data Structures 93 1
C++ Segment Trees 321 2
C++ Trie Cost of Data 290 1
C++ Trie Datastructure 278 1
C++ Greedy Approach Minimum number of coins 525 0
C++ Greedy Approach Maximum height Pyramid 328 1
C++ Greedy Approach String lexicographically largest subsequence 246 0
C++ Greedy Approach Lexicographically largest subsequence 364 0
C++ Greedy Approach Prims MST 398 1
C++ Greedy Approach Krushkals MST 457 1
C++ Greedy Approach N-array maximum sum 333 1
C++ Greedy Approach Policemen Catch Thieves 563 1
C++ Greedy Approach Maximum product Subset 546 1
C++ Greedy Approach Minimum Product Subset 348 1
C++ Greedy Approach Fractional Knapsack 737 1
C++ Greedy Approach-Activity Selection Problem 744 1
C++ Greedy Approach-Egyptian Fractions 639 0
C++ Greedy Approach-Huffman Codes 1031 1
C++ Introduction to Greedy Approach 955 2