Make String a Subsequence Using Cyclic Increments

Make String a Subsequence Using Cyclic Increments - 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.

Input & Output

Example 1 — Basic Match

$ Input: str1 = "abc", str2 = "acd"

› Output: true

💡 Note: We can increment str1[2] from 'c' to 'd', making str1 = "abd". Then "acd" is a subsequence: 'a' matches str1[0], 'c' is skipped, 'd' matches str1[2].

Example 2 — No Match Possible

$ Input: str1 = "zc", str2 = "ad"

› Output: false

💡 Note: Even with increments: 'z'→'a' and 'c'→'d' gives "ad", but we need "ad" as subsequence. Since both characters are used, we can't form the subsequence.

Example 3 — Cyclic Wrap Around

$ Input: str1 = "za", str2 = "aa"

› Output: true

💡 Note: We can increment str1[0] from 'z' to 'a' (cyclic), making str1 = "aa". Then "aa" is a subsequence of "aa".

Constraints

1 ≤ str1.length, str2.length ≤ 10⁵
str1 and str2 consist of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Strings

str1 = "abc", str2 = "acd"

Apply Increments

Increment 'c' to 'd' cyclically (c + 1 = d)

Check Subsequence

"acd" is subsequence of modified "abd"

Key Takeaway

🎯 Key Insight: Use greedy two-pointer matching - each character can stay same or increment by one

Asked in

G Google 15 M Meta 12 a Amazon 10

The key insight is that each character can either stay the same or be incremented by one cyclically. The optimal approach uses two pointers to greedily match characters in a single pass. Time: O(n + m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Greedy Matching	O(n + m)	O(1)	Use two pointers to greedily match characters, allowing at most one increment per character
Brute Force - Try All Combinations	O(2^n × m)	O(n)	Generate all possible strings by trying every combination of character increments

Two Pointers - Greedy Matching — Algorithm Steps

Initialize two pointers for str1 and str2
For each character in str2, find the next matching character in str1
A match occurs if characters are equal OR if str1 char + 1 equals str2 char
Return true if all characters in str2 are matched

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Pointers

Set pointers i=0 for str1, j=0 for str2

Match Characters

For each position, check direct match or increment match

Advance Pointers

Move i always, move j only on successful match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* str1, char* str2) {
    int i = 0, j = 0;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    
    while (i < len1 && j < len2) {
        // Check if characters match directly
        if (str1[i] == str2[j]) {
            j++;
        }
        // Check if incrementing str1[i] matches str2[j]
        else {
            char nextChar = (str1[i] - 'a' + 1) % 26 + 'a';
            if (nextChar == str2[j]) {
                j++;
            }
        }
        i++;
    }
    
    return j == len2;
}

int main() {
    char str1[1001], str2[1001];
    fgets(str1, sizeof(str1), stdin);
    str1[strcspn(str1, "\n")] = 0;
    fgets(str2, sizeof(str2), stdin);
    str2[strcspn(str2, "\n")] = 0;
    
    bool result = solution(str1, str2);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through both strings with two pointers

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~18 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Greedy Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler