Make String a Subsequence Using Cyclic Increments

Med

#2525Time: 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.

Patterns

Two Pointers

Data structures

String

Prompt

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 <= 10⁵
1 <= str2.length <= 10⁵
str1 and str2 consist of only lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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]:

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.
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()].

1class Solution {2    public boolean canMakeSubsequence(String str1, String str2) {3        int n = str1.length();4        int m = str2.length();5        boolean[][] dp = new boolean[n + 1][m + 1];6 7        for (int i = 0; i <= n; i++) {8            dp[i][0] = true;9        }10 11        for (int i = 1; i <= n; i++) {12            for (int j = 1; j <= m; j++) {13                char c1 = str1.charAt(i - 1);14                char c2 = str2.charAt(j - 1);15                char next_c1 = (char) (((c1 - 'a' + 1) % 26) + 'a');16                17                dp[i][j] = dp[i - 1][j];18                19                if (c1 == c2 || next_c1 == c2) {20                    dp[i][j] = dp[i][j] || dp[i - 1][j - 1];21                }22            }23        }24        return dp[n][m];25    }26}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean canMakeSubsequence(String str1, String str2) {3        int i = 0; // pointer for str14        int j = 0; // pointer for str25        int n = str1.length();6        int m = str2.length();7 8        while (i < n && j < m) {9            char c1 = str1.charAt(i);10            char c2 = str2.charAt(j);11            12            char next_c1 = (char) (((c1 - 'a' + 1) % 26) + 'a');13            14            if (c1 == c2 || next_c1 == c2) {15                j++;16            }17            i++;18        }19 20        return j == m;21    }22}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution:2    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)

1class Solution {2public3  boolean canMakeSubsequence(String str1, String str2) {4    int i = 0, n = str2.length();5    for (char c : str1.toCharArray()) {6      char d = c == 'z' ? 'a' : (char)(c + 1);7      if (i < n && (str2.charAt(i) == c || str2.charAt(i) == d)) {8        ++i;9      }10    }11    return i == n;12  }13}

1class Solution {2public:3  bool canMakeSubsequence(string str1, string str2) {4    int i = 0, n = str2.size();5    for (char c : str1) {6      char d = c == 'z' ? 'a' : c + 1;7      if (i < n && (str2[i] == c || str2[i] == d)) {8        ++i;9      }10    }11    return i == n;12  }13};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem