Leetcode 2825: Make String a Subsequence Using Cyclic Increments

Input: Two strings `str1` and `str2` consisting only of lowercase English letters.

Example: str1 = 'abc', str2 = 'ad'

Constraints:

• 1 <= str1.length <= 10^5

• 1 <= str2.length <= 10^5

• str1 and str2 consist of only lowercase English letters.

Output: Return `true` if it is possible to make `str2` a subsequence of `str1` by performing the operation at most once, otherwise return `false`.

Example: For `str1 = 'abc'`, `str2 = 'ad'`, the output should be `true`.

Constraints:

Goal: The task is to check if `str2` can be a subsequence of `str1` after performing the operation once.

Steps:

• Loop through the characters of `str1` and try to match them with `str2`.

• If a match is found, check if the character in `str1` can be incremented to match the character in `str2`.

Goal: Constraints on the lengths and content of `str1` and `str2`.

Steps:

• Both `str1` and `str2` are non-empty.

• The strings consist only of lowercase English letters.

Assumptions:

• The strings consist only of lowercase English letters.

• The operation can be applied at most once.

• Input: For `str1 = 'abc'`, `str2 = 'ad'`

• Explanation: By incrementing the character at index 2 in `str1` to 'd', `str1` becomes 'abd' and `str2` is now a subsequence of `str1`.

Approach: The solution involves checking if the characters in `str2` can be matched with `str1` by performing the operation at most once.

Observations:

• Both strings consist of lowercase English letters.

• We can increment characters in `str1` to try and match `str2`.

• The matching needs to be done in sequence, and we should only increment characters when necessary.

Steps:

• Initialize an index pointer for `str2`.

• Iterate over each character in `str1`.

• If characters in `str1` and `str2` match directly or by incrementing, move the pointer in `str2`.

• Return `true` if the pointer reaches the end of `str2`.

Empty Inputs:

• If `str2` is empty, return `true` immediately.

Large Inputs:

• Ensure the solution works efficiently for the maximum input sizes.

Special Values:

• If `str1` and `str2` are already the same, return `true`.

Constraints:

• Handle large inputs within time limits.

bool canMakeSubsequence(string s1, string s2) {
    int j = 0, n = s1.size(), m = s2.size();
    for (int i = 0; i < n && j < m; ++i)
        if (s1[i] == s2[j] || s1[i] + 1 == s2[j] || s1[i] - 25 == s2[j])
            ++j;
    return j == m;
}

1 : Function Definition

bool canMakeSubsequence(string s1, string s2) {

The function 'canMakeSubsequence' is defined, taking two strings 's1' and 's2' as input. It returns a boolean value indicating whether 's2' can be formed as a subsequence of 's1'.

2 : Variable Initialization

    int j = 0, n = s1.size(), m = s2.size();

Variables 'j', 'n', and 'm' are initialized. 'j' is used to track the position in 's2', while 'n' and 'm' store the lengths of 's1' and 's2', respectively.

3 : Loop Start

    for (int i = 0; i < n && j < m; ++i)

A for loop starts, iterating through each character of 's1'. The loop continues as long as 'j' is less than the length of 's2' and 'i' is within the bounds of 's1'.

4 : Condition Check

        if (s1[i] == s2[j] || s1[i] + 1 == s2[j] || s1[i] - 25 == s2[j])

A condition checks if the current character in 's1' is equal to the current character in 's2', or if they are consecutive characters in the alphabet (either 's1[i] + 1' or 's1[i] - 25' equals 's2[j]').

5 : Update Index

            ++j;

If the condition is true, increment 'j' to move to the next character in 's2'.

6 : Return Statement

    return j == m;

Return true if all characters in 's2' have been matched in sequence; otherwise, return false.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), where n is the length of `str1`.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1), as we only use a few extra variables.

Leetcode 2825: Make String a Subsequence Using Cyclic Increments

Explore →