2825. Make String a Subsequence Using Cyclic Increments

Problem Statement

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.

Intuition

Just match the string and check if, not matches exactly , incr by 1 and try to match

Links

https://leetcode.com/problems/make-string-a-subsequence-using-cyclic-increments/description/

Video Links

Approach 1:

Earlier 

C++

class Solution {
public:
    bool canMakeSubsequence(string s, string t) {
        int i = s.size()-1;
        int j = t.size()-1;

        while(i>=0 and j>=0){
            if(s[i] == t[j] or s[i]+1 == t[j] or (s[i]=='z' and t[j]=='a')){
                i--;
                j--;
            }

            else
                i--;
        }

        if(j<0)
            return true;

        return false;
    }
};

Approach 2:

New

C++

class Solution {
public:
    bool canMakeSubsequence(string s, string t) {
        int i = s.size()-1;
        int j = t.size()-1;

        while(i>=0 and j>=0){
            if(s[i] == t[j]){
                j--;
            }

            else{
                int idx = s[i]-'a';
                int new_idx = (idx + 1)%26;

                char ch = char(new_idx + 'a');

                if(ch == t[j])
                    j--;    
            }

            i--;
        }

        return j<0;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems