In this problem we have to check. whether two strings can be made equal by increasing the ASCII value of characters of the prefix of first string. We can increase different prefixes multiple times.
The strings consists of only lowercase alphabets and does not contain any special characters .
Examples:
Input : string 1=”abcd”, string 2=”bcdd”
Output : Yes
Explanation : The string 1 can be converted to string 2 by increasing the prefix of string_1 by 1 i.e. increasing the ASCII value of the prefix string of “abcd”, “abc” by 1 .
In this way we can convert “abcd” to “bcdd”Input :string 1=”abcd”, string 2=”bcdg”
Output :No
Solution: Two strings can be made equal to each other by increasing the ASCII value of the prefix of the first string only when all the ASCII values of the first string is less than or equal to the second string and the difference of ASCII values of characters are in descending order.
So we will check if both the strings are equal or not, if they are equal then we will check that all the ASCII values of first string is less than or equal to the second string or not, and we will create a different array that will store the difference of characters of two strings and check if the difference array is in descending order or not, if all the conditions are satisfied we will print “Yes” else “No”.
Implementation:
C++
// C++ implementation of above approach#include <iostream>using namespace std;// check whether the first string can be// converted to the second string// by increasing the ASCII value of prefix// string of first stringbool find(string s1, string s2){ // length of two strings int len = s1.length(), len_1 = s2.length(); // If lengths are not equal if (len != len_1) return false; // store the difference of ASCII values int d[len] = { 0 }; // difference of first element d[0] = s2[0] - s1[0]; // traverse through the string for (int i = 1; i < len; i++) { // the ASCII value of the second string // should be greater than or equal to first // string, if it is violated return false. if (s1[i] > s2[i]) return false; else { // store the difference of ASCII values d[i] = s2[i] - s1[i]; } } // the difference of ASCII values should be // in descending order for (int i = 0; i < len - 1; i++) { // if the difference array is not in descending order if (d[i] < d[i + 1]) return false; } // if all the ASCII values of characters of first string // is less than or equal to the second string // and the difference array is in descending // order, return true return true;}// Driver codeint main(){ // create two strings string s1 = "abcd", s2 = "bcdd"; // check whether the first string can be // converted to the second string if (find(s1, s2)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of above approach class GFG { // check whether the first string can be // converted to the second string // by increasing the ASCII value of prefix // string of first string static boolean find(String s1, String s2) { // length of two strings int len = s1.length(), len_1 = s2.length(); // If lengths are not equal if (len != len_1) { return false; } // store the difference of ASCII values int d[] = new int[len]; // difference of first element d[0] = s2.charAt(0) - s1.charAt(0); // traverse through the string for (int i = 1; i < len; i++) { // the ASCII value of the second string // should be greater than or equal to first // string, if it is violated return false. if (s1.charAt(i) > s2.charAt(i)) { return false; } else { // store the difference of ASCII values d[i] = s2.charAt(i) - s1.charAt(i); } } // the difference of ASCII values should be // in descending order for (int i = 0; i < len - 1; i++) { // if the difference array is not in descending order if (d[i] < d[i + 1]) { return false; } } // if all the ASCII values of characters // of first string is less than or equal to // the second string and the difference array // is in descending order, return true return true; } // Driver code public static void main(String[] args) { // create two strings String s1 = "abcd", s2 = "bcdd"; // check whether the first string can be // converted to the second string if (find(s1, s2)) { System.out.println("Yes"); } else { System.out.println("No"); } }}// This code is contributed by PrinciRaj1992 |
C#
// C# implementation of above approachusing System;class GFG{ // check whether the first string can be// converted to the second string// by increasing the ASCII value of prefix// string of first stringpublic static bool find(string s1, string s2){ // length of two strings int len = s1.Length, len_1 = s2.Length; // If lengths are not equal if (len != len_1) return false; // store the difference of ASCII values int []d = new int [len]; // difference of first element d[0] = s2[0] - s1[0]; // traverse through the string for (int i = 1; i < len; i++) { // the ASCII value of the second string // should be greater than or equal to first // string, if it is violated return false. if (s1[i] > s2[i]) return false; else { // store the difference of ASCII values d[i] = s2[i] - s1[i]; } } // the difference of ASCII values should be // in descending order for (int i = 0; i < len - 1; i++) { // if the difference array is not in descending order if (d[i] < d[i + 1]) return false; } // if all the ASCII values of characters of first string // is less than or equal to the second string // and the difference array is in descending // order, return true return true;}// Driver codepublic static void Main(){ // create two strings string s1 = "abcd", s2 = "bcdd"; // check whether the first string can be // converted to the second string if (find(s1, s2)) Console.WriteLine("Yes"); else Console.WriteLine( "No");}}// This code is contributed by SoM15242 |
Python3
# Python 3 implementation of above approach# check whether the first string can be# converted to the second string# by increasing the ASCII value of prefix# string of first stringdef find(s1, s2): # length of two strings len__ = len(s1) len_1 = len(s2) # If lengths are not equal if (len__ != len_1): return False # store the difference of ASCII values d = [0 for i in range(len__)] # difference of first element d[0] = ord(s2[0]) - ord(s1[0]) # traverse through the string for i in range(1, len__, 1): # the ASCII value of the second string # should be greater than or equal to first # string, if it is violated return false. if (s1[i] > s2[i]): return False else: # store the difference of ASCII values d[i] = ord(s2[i]) - ord(s1[i]) # the difference of ASCII values # should be in descending order for i in range(len__ - 1): # if the difference array is not # in descending order if (d[i] < d[i + 1]): return False # if all the ASCII values of characters of # first string is less than or equal to the # second string and the difference array is # in descending order, return true return True# Driver codeif __name__ == '__main__': # create two strings s1 = "abcd" s2 = "bcdd" # check whether the first string can # be converted to the second string if (find(s1, s2)): print("Yes") else: print("No")# This code is contributed by# Shashank_Sharma |
Javascript
<script>// Javascript implementation of above approach// check whether the first string can be// converted to the second string// by increasing the ASCII value of prefix// string of first stringfunction find(s1, s2){ // length of two strings var len = s1.length, len_1 = s2.length; // If lengths are not equal if (len != len_1) return false; // store the difference of ASCII values var d = Array(len).fill(0); // difference of first element d[0] = s2[0] - s1[0]; // traverse through the string for (var i = 1; i < len; i++) { // the ASCII value of the second string // should be greater than or equal to first // string, if it is violated return false. if (s1[i] > s2[i]) return false; else { // store the difference of ASCII values d[i] = s2[i] - s1[i]; } } // the difference of ASCII values should be // in descending order for (var i = 0; i < len - 1; i++) { // if the difference array is not in descending order if (d[i] < d[i + 1]) return false; } // if all the ASCII values of characters of first string // is less than or equal to the second string // and the difference array is in descending // order, return true return true;}// Driver code// create two stringsvar s1 = "abcd", s2 = "bcdd";// check whether the first string can be// converted to the second stringif (find(s1, s2)) document.write( "Yes");else document.write( "No");</script> |
Output
Yes
Complexity analysis:
- Time Complexity: O(N), where N is the length of s1 string
- Auxiliary Space: O(N), where N is the length of s1 string
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
