Make String a Subsequence Using Cyclic Increments

Make String a Subsequence Using Cyclic Increments

What is this problem about?

In this problem, you are given two strings, str1 and str2. You are allowed to perform an operation on str1 at most once: you can select a set of indices and cyclically increment the characters at those indices (e.g., 'a' becomes 'b', 'z' becomes 'a'). Your goal is to determine if you can make str2 a subsequence of str1 by applying this operation.

Why is this asked in interviews?

This is a standard Two Pointers string problem wrapped in a slight logical twist. Interviewers ask it to test if a candidate can adapt the classic "is subsequence" algorithm to accommodate a flexible matching condition. It evaluates your ability to handle modular arithmetic for character wrapping and write clean, linear-time traversals without getting bogged down by the "set of indices" wording.

Algorithmic pattern used

This problem strictly uses the Two Pointers pattern. Because the problem states you can pick any set of indices to increment, you essentially have the power to optionally increment any character you want in str1 exactly once. Therefore, you use a pointer i for str1 and j for str2. You advance j if str1[i] exactly matches str2[j], OR if str1[i] incremented by one matches str2[j]. You always advance i. If j reaches the end of str2, it's a valid subsequence.

Example explanation

str1 = "abc", str2 = "ad"

• i=0 ('a'), j=0 ('a'): 'a' matches 'a'. Advance both. i=1, j=1.
• i=1 ('b'), j=1 ('d'): 'b' != 'd'. Incremented 'b' is 'c'. 'c' != 'd'. No match. Advance i only. i=2, j=1.
• i=2 ('c'), j=1 ('d'): 'c' != 'd'. Incremented 'c' is 'd'. 'd' == 'd'! Match! Advance both. i=3, j=2. Pointer j reached length of str2 (2). We return true.

Common mistakes candidates make

Candidates often get confused by the phrasing "select a set of indices" and attempt to pre-calculate all possible strings, which is impossible due to combinations. The realization that you can evaluate the increment on-the-fly during traversal is key. Another common error is messing up the cyclic increment for 'z'. ('z' + 1) in ASCII is {, not 'a'. You must explicitly map 'z' to 'a' or use modular arithmetic ((char - 'a' + 1) % 26) + 'a'.

Interview preparation tip

When solving the Make String a Subsequence interview question, write a tiny helper function or inline logic: boolean match(c1, c2) { return c1 == c2 || (c1 == 'z' ? 'a' : c1 + 1) == c2; }. Using this helper inside a standard Two Pointers while loop makes your code incredibly clean and immediately proves to the interviewer that you understand the core cyclic constraint.