Make String a Subsequence Using Cyclic Increments | Leetcode 2825 solution

 2825. Make String a Subsequence Using Cyclic Increments

You are given two 0-indexed strings str1 and str2.

In an operation, you select a set of indices in str1, and for each index i in the set, increment str1[i] to the next character cyclically. That is 'a' becomes 'b', 'b' becomes 'c', and so on, and 'z' becomes 'a'.

Return true if it is possible to make str2 a subsequence of str1 by performing the operation at most once, and false otherwise.

Note: A subsequence of a string is a new string that is formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

 

Example 1:

Input: str1 = "abc", str2 = "ad"
Output: true
Explanation: Select index 2 in str1.
Increment str1[2] to become 'd'. 
Hence, str1 becomes "abd" and str2 is now a subsequence. Therefore, true is returned.

Example 2:

Input: str1 = "zc", str2 = "ad"
Output: true
Explanation: Select indices 0 and 1 in str1. 
Increment str1[0] to become 'a'. 
Increment str1[1] to become 'd'. 
Hence, str1 becomes "ad" and str2 is now a subsequence. Therefore, true is returned.

Example 3:

Input: str1 = "ab", str2 = "d"
Output: false
Explanation: In this example, it can be shown that it is impossible to make str2 a subsequence of str1 using the operation at most once. 
Therefore, false is returned.

 

Constraints:

• 1 <= str1.length <= 105
• 1 <= str2.length <= 105
• str1 and str2 consist of only lowercase English letters.

Solution : 

Code Explanation:

1. The code defines a C++ class named Solution which encapsulates the functionality to check if one string can be transformed into another as a subsequence.

2. 
   

3. The check function is a recursive helper function that takes two strings (str1 and str2) and two indices (i and j) as arguments. It checks if str1 can be transformed into str2 by iterating through both strings from right to left. The function returns true if the transformation is possible and false otherwise.

4. 
   

5. In the canMakeSubsequence function, the code calculates the lengths of the input strings (str1 and str2) and initializes indices i and j accordingly.

6. 
   

7. It then calls the check function with the provided arguments, and if the result is true, it means that str1 can be transformed into str2 as a subsequence, and the function returns true. Otherwise, it returns false.

class Solution { public:     bool check(string &str1, string &str2 , int i, int j)     {          if(j == -1)         {             return true;         }         if(i == -1)         {             return false;         }         if(str2[j] == str1[i] || (str1[i] +1) == str2[j] || (str1[i] == 'z' && str2[j] == 'a') )         {             if(check(str1 , str2 , i-1 , j-1))                 return true;                     }         else         return check(str1 , str2 , i-1, j );               return false;           }     bool canMakeSubsequence(string str1, string str2) {                 int i = str1.length() -1 ;         int j = str2.length() - 1;         if(check(str1 , str2 , i, j))             return true;         return false;           } };