Scale Engineer

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 <= 105
  • 1 <= str2.length <= 105
  • 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]:

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

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.

Solutions

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)

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 →

Next problem