Make String a Subsequence Using Cyclic Increments

medium two pointers string greedy

Problem

You are given two 0-indexed strings str1 and str2. In one operation you pick any set of indices in str1 and increment each chosen character cyclically to the next letter (‘a’→‘b’, …, ‘z’→‘a’). Return true if, after performing the operation at most once, str2 can be made a subsequence of str1; otherwise return false.

A subsequence keeps the relative order of the remaining characters after deleting some (possibly none) of them. Because each index can be incremented at most once, the character at str1[i] can match str2[j] either as-is, or after a single cyclic +1.

Inputstr1 = "abc", str2 = "ad"

Outputtrue

Increment index 2: 'c' becomes 'd'. Then str1 = "abd" and "ad" is a subsequence.

str1 (lowercase letters)

str2 (lowercase letters)

def canMakeSubsequence(str1, str2):
    j = 0                                    # pointer into str2
    n = len(str2)
    for ch in str1:                          # scan every character of str1
        if j == n:                           # str2 already fully matched
            break
        nxt = chr((ord(ch) - 97 + 1) % 26 + 97)  # cyclic next letter
        if ch == str2[j] or nxt == str2[j]:  # match as-is or after one increment
            j += 1                           # consume one char of str2
    return j == n                            # true iff all of str2 matched

function canMakeSubsequence(str1, str2) {
  let j = 0;                                 // pointer into str2
  const n = str2.length;
  for (const ch of str1) {                   // scan every character of str1
    if (j === n) break;                      // str2 already fully matched
    const c = ch.charCodeAt(0) - 97;
    const nxt = String.fromCharCode((c + 1) % 26 + 97); // cyclic next letter
    if (ch === str2[j] || nxt === str2[j]) { // match as-is or after one increment
      j++;                                   // consume one char of str2
    }
  }
  return j === n;                            // true iff all of str2 matched
}

boolean canMakeSubsequence(String str1, String str2) {
    int j = 0;                               // pointer into str2
    int n = str2.length();
    for (int i = 0; i < str1.length(); i++) {// scan every character of str1
        if (j == n) break;                   // str2 already fully matched
        char ch = str1.charAt(i);
        char nxt = (char) ((ch - 'a' + 1) % 26 + 'a'); // cyclic next letter
        if (ch == str2.charAt(j) || nxt == str2.charAt(j)) { // match or +1
            j++;                             // consume one char of str2
        }
    }
    return j == n;                           // true iff all of str2 matched
}

bool canMakeSubsequence(string str1, string str2) {
    int j = 0;                               // pointer into str2
    int n = str2.size();
    for (char ch : str1) {                   // scan every character of str1
        if (j == n) break;                   // str2 already fully matched
        char nxt = (char) ((ch - 'a' + 1) % 26 + 'a'); // cyclic next letter
        if (ch == str2[j] || nxt == str2[j]) {// match as-is or after one increment
            j++;                             // consume one char of str2
        }
    }
    return j == n;                           // true iff all of str2 matched
}

Explanation

This is a greedy two-pointer matching. We never need to decide a global set of increments up front: each index in str1 can be incremented independently and at most once, so a single character str1[i] can stand in for str2[j] in exactly two situations — it already equals str2[j], or its cyclic successor equals str2[j].

Pointer j tracks how much of str2 has been matched so far. We sweep str1 left to right. Whenever the current character can cover str2[j] (as-is or via one cyclic +1), we “use” it and advance j; otherwise we skip that character of str1 and move on. The scan of str1 advances on every iteration regardless.

The greedy choice is safe: matching str2[j] at the earliest possible position in str1 never hurts, because it leaves the longest possible remaining suffix of str1 for the rest of str2. So if any valid embedding exists, this earliest-match scan finds one.

The cyclic successor of a letter is computed with modular arithmetic: (ch - 'a' + 1) % 26 + 'a'. This makes 'z' wrap to 'a' without any special case.

We succeed exactly when j reaches len(str2) — every character of str2 was matched in order. Example: str1 = "abc", str2 = "ad". 'a' matches 'a' (j→1); 'b' cannot cover 'd'; 'c' increments to 'd' and matches (j→2). j reached 2 = len(str2), so the answer is true.

Time: O(|str1| + |str2|) Space: O(1)