# Make String a Subsequence Using Cyclic Increments
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/make-string-a-subsequence-using-cyclic-increments)
Canonical: https://scaleengineer.com/dsa/problems/make-string-a-subsequence-using-cyclic-increments
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## Problem
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.

# Approaches
## Dynamic Programming Approach
This approach uses dynamic programming to solve the problem, which is a standard technique for subsequence problems. We build a 2D table `dp` where `dp[i][j]` represents whether the first `j` characters of `str2` can be formed as a subsequence from the first `i` characters of `str1`, considering the cyclic increment rule.
**Time:** O(N * M), where N is the length of `str1` and M is the length of `str2`. We fill a 2D DP table of size N x M. · **Space:** O(N * M) for the DP table. This can be optimized to O(M) by only storing the previous row's results.
**Pros:** It's a standard and systematic way to solve subsequence problems.; The logic is relatively straightforward to understand for those familiar with DP.
**Cons:** High time complexity, which will result in a 'Time Limit Exceeded' (TLE) error given the constraints (N, M <= 10^5).; High space complexity, although it can be optimized.
### Explanation
We define a 2D boolean array `dp` of size `(str1.length() + 1) x (str2.length() + 1)`. `dp[i][j]` will be `true` if `str2.substring(0, j)` is a subsequence of `str1.substring(0, i)` under the given operation, and `false` otherwise. The base case is that an empty `str2` is a subsequence of any prefix of `str1`, so `dp[i][0]` is `true` for all `i`. We iterate through `str1` (from `i = 1` to `N`) and `str2` (from `j = 1` to `M`). For each `dp[i][j]`, we determine its value based on two possibilities for the character `str1[i-1]`:
1. We don't use `str1[i-1]` to match `str2[j-1]`. In this case, `dp[i][j]` is `true` if `dp[i-1][j]` is `true`.
2. We use `str1[i-1]` to match `str2[j-1]`. This is possible only if `str1[i-1]` is equal to `str2[j-1]` or its cyclic increment is equal to `str2[j-1]`. If this condition holds, `dp[i][j]` can also be `true` if `dp[i-1][j-1]` is `true`.
The recurrence relation is: `dp[i][j] = dp[i-1][j] || (can_match(str1[i-1], str2[j-1]) && dp[i-1][j-1])`. The final answer is `dp[str1.length()][str2.length()]`.

```java
class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();
        boolean[][] dp = new boolean[n + 1][m + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c1 = str1.charAt(i - 1);
                char c2 = str2.charAt(j - 1);
                char next_c1 = (char) (((c1 - 'a' + 1) % 26) + 'a');
                
                dp[i][j] = dp[i - 1][j];
                
                if (c1 == c2 || next_c1 == c2) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - 1];
                }
            }
        }
        return dp[n][m];
    }
}
```
### Algorithm
- Create a DP table `dp` of size `(N+1) x (M+1)`, where `N` is `str1.length()` and `M` is `str2.length()`.
- Initialize the first column `dp[i][0]` to `true` for all `i`, as an empty string is always a subsequence.
- Iterate `i` from 1 to `N`.
- Inside, iterate `j` from 1 to `M`.
- For each cell `(i, j)`, first assume we don't use `str1[i-1]`, so `dp[i][j] = dp[i-1][j]`.
- Then, check if `str1[i-1]` can match `str2[j-1]` (either directly or with one increment).
- If it can match, we have another option: `dp[i][j] = dp[i][j] || dp[i-1][j-1]`.
- After filling the table, `dp[N][M]` holds the final answer.

## Greedy Two-Pointer Approach
This is a highly efficient approach that uses a greedy strategy with two pointers. We iterate through `str1` and try to match the characters of `str2` in order. Since we want to find *any* valid subsequence, it's always optimal to match the current character of `str2` with the earliest possible character in `str1`.
**Time:** O(N), where N is the length of `str1`. In the worst case, we iterate through `str1` once. · **Space:** O(1), as we only use a constant amount of extra space for the pointers.
**Pros:** Extremely efficient in both time and space.; Simple and intuitive to implement.; Optimal solution for the given constraints.
**Cons:** The correctness of the greedy choice might not be immediately obvious without reasoning about the nature of subsequences.
### Explanation
We use two pointers, `i` for `str1` and `j` for `str2`, both initialized to 0. The pointer `i` iterates through `str1` from beginning to end. The pointer `j` tracks the current character we are looking for from `str2`. In each step, we check if the character `str1[i]` can match `str2[j]`. A match occurs if `str1[i]` is the same as `str2[j]`, or if `str1[i]` cyclically incremented by one becomes `str2[j]`. The condition for a match is `str1.charAt(i) == str2.charAt(j)` or `(str1.charAt(i) - 'a' + 1) % 26 == (str2.charAt(j) - 'a')`. If a match is found, it means we have successfully placed the `j`-th character of `str2` in our subsequence. We then advance the `j` pointer to look for the next character of `str2`. We always advance the `i` pointer, regardless of whether a match was found. The process continues until we either exhaust `str1` or we have found all characters of `str2`. If `j` reaches the length of `str2`, it means we have found a valid subsequence, and we return `true`. Otherwise, we return `false`.

```java
class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int i = 0; // pointer for str1
        int j = 0; // pointer for str2
        int n = str1.length();
        int m = str2.length();

        while (i < n && j < m) {
            char c1 = str1.charAt(i);
            char c2 = str2.charAt(j);
            
            char next_c1 = (char) (((c1 - 'a' + 1) % 26) + 'a');
            
            if (c1 == c2 || next_c1 == c2) {
                j++;
            }
            i++;
        }

        return j == m;
    }
}
```
### Algorithm
- Initialize a pointer `j = 0` for `str2`.
- Iterate through `str1` with a pointer `i` from 0 to `str1.length() - 1`.
- Inside the loop, if `j` has already reached `str2.length()`, we can stop early.
- Let `c1 = str1.charAt(i)` and `c2 = str2.charAt(j)`.
- Check if `c1` can match `c2` (i.e., `c1 == c2` or its cyclic successor `next_char(c1) == c2`).
- If it's a match, we've found the character `str2[j]`, so we increment `j` to look for the next one.
- We always increment `i` to move to the next character in `str1`.
- After the loop finishes, if `j == str2.length()`, it means we found all characters. Return `true`.
- Otherwise, return `false`.

# Solutions
### Python

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

```

### Java

```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;
  }
}

```

### CPP

```cpp
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;
  }
};

```