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.

Approach 01:

#include <string>
using namespace std;

class Solution {
public:
    bool canMakeSubsequence(const string &sourceString, const string &targetString) {
        int targetIndex = 0; // Index for targetString

        for (char sourceChar : sourceString) {
            // Check if the current character matches or can rotate to match
            if (sourceChar == targetString[targetIndex] || 
                ('a' + (sourceChar - 'a' + 1) % 26) == targetString[targetIndex]) {
                targetIndex++;
                if (targetIndex == targetString.length())
                    return true;
            }
        }

        return false;
    }
};

import string

class Solution:
    def canMakeSubsequence(self, sourceString: str, targetString: str) -> bool:
        targetIndex = 0  # Index for targetString

        for sourceChar in sourceString:
            # Check if the current character matches or can rotate to match
            if (sourceChar == targetString[targetIndex] or 
                chr(ord('a') + (string.ascii_lowercase.index(sourceChar) + 1) % 26) == targetString[targetIndex]):
                targetIndex += 1
                if targetIndex == len(targetString):
                    return True

        return False

Time Complexity

• Iterating through the source string:

  The function iterates over each character of sourceString. If the length of sourceString is \(N\), this operation takes \(O(N)\).

• Character checks:

  For each character in sourceString, the function checks if it matches the current character in targetString or can rotate to match. These checks are \(O(1)\) operations performed \(N\) times.

• Overall Time Complexity:

  The total time complexity is \(O(N)\), as all operations are linear with respect to the length of sourceString.

Space Complexity

• Input strings:

  The input strings sourceString and targetString are part of the input and do not contribute to additional space usage.

• Auxiliary variables:

  The function uses a single integer variable targetIndex and temporary variables for character comparisons, all of which require \(O(1)\) space.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\), as no additional data structures are used.