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.

C++

• class Solution {
  public:
      bool canMakeSubsequence(string str1, string str2) {
          int i = 0, n = str2.size();
          for (char c : str1) {
              char d = c == 'z' ? 'a' : c + 1;
              if (i < n && (str2[i] == c || str2[i] == d)) {
                  ++i;
              }
          }
          return i == n;
      }
  };

JAVA

• class Solution {
      public boolean canMakeSubsequence(String str1, String str2) {
          int i = 0, n = str2.length();
          for (char c : str1.toCharArray()) {
              char d = c == 'z' ? 'a' : (char) (c + 1);
              if (i < n && (str2.charAt(i) == c || str2.charAt(i) == d)) {
                  ++i;
              }
          }
          return i == n;
      }
  }

PYTHON

• class Solution:
      def canMakeSubsequence(self, str1: str, str2: str) -> bool:
          i, n = 0, len(str2)
          for c in str1:
              d = 'a' if c == 'z' else chr(ord(c) + 1)
              if i < n and (str2[i] == c or str2[i] == d):
                  i += 1
          return i == n