Vultr DocsLatest Content

Make String a Subsequence Using Cyclic Increments

Updated on 05 June, 2025
Make String a Subsequence Using Cyclic Increments header image

Problem Statement

In this problem, two 0-indexed strings str1 and str2 are provided. The objective is to determine if str2 can be made a subsequence of str1 by performing a specific operation at most once on str1. This operation involves selecting a set of indices in str1 and incrementing each character at these indices to its next character cyclically, where after 'z', the cycle continues back to 'a'. For instance, if a character at an index is 'a', it will become 'b' and so forth. A subsequence is defined as a derivative string formed without rearranging the order but potentially removing some characters from the original string. The task is to return true if the transformation allows str2 to be a subsequence of str1; otherwise, return false.

Examples

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.

Approach and Intuition

The challenge essentially involves checking whether we can transform str1 into a form where str2 can be derived as its subsequence with at most one pass of transformations on specified indices. We can break down the approach as follows:

  1. Cyclic Character Transformation:

    • For each character in str1, assess the potential character it could transform into if the character cycles once. This involves a simple mapping where each letter moves to the next, and 'z' returns to 'a'.

  2. Subsequence Check:

    • Using the transformed versions of str1 from the cyclic operation, verify if str2 can be a subsequence. This subsequence check should ideally move sequentially through both strings, trying to match characters of str2 with those of str1.

  3. Edge Cases:

    • Only a single operation is allowed; hence all necessary index changes for transformation should be kept within this limit.
    • Consider cases where str2 is inherently already a subsequence without any operations. This requires a direct comparison before the expensive operation.
    • Address scenarios where transformations can lead to potential sequences forming in parts of the strings that do not require modification or only small sections do.

From the given examples:

  • In Example 3, str2 is "d" which cannot be formed from "ab" since neither 'a' nor 'b' can become 'd' with a single cyclic increment, resulting in "false".
  • Examples 1 and 2 demonstrate scenarios where strategic increments at selected indices successfully allow str2 to be a subsequence post-transformation.

In essence, the solution needs to evaluate the potential transformation outcomes against the subsequence condition efficiently, adhering to the provided constraints.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    bool validateSubsequence(string s1, string s2) {
        int indexS2 = 0;
        int len1 = s1.length(), len2 = s2.length();
    
        for (int indexS1 = 0; indexS1 < len1 && indexS2 < len2; ++indexS1) {
            if (s1[indexS1] == s2[indexS2] ||
                (s1[indexS1] + 1 == s2[indexS2]) ||
                (s1[indexS1] - 25 == s2[indexS2])) {
                indexS2++;
            }
        }
        return indexS2 == len2;
    }
};

The provided C++ solution focuses on verifying if string s2 can be transformed into a subsequence of string s1 by using cyclic increments. To achieve this, the function validateSubsequence loops through each character of s1 to check if there is a match with the current character of s2 under three conditions:

  • Direct character match between s1[indexS1] and s2[indexS2].
  • The character in s1 is one less than that in s2, allowing for an increment to match.
  • The character in s1 is the alphabetically last (i.e., 'z'), and the character in s2 is the alphabetically first (i.e., 'a'), treating the relationship cyclically with a +1 increment.

The incrementing is deemed cyclic because on reaching 'z', it loops back to 'a'. If any of these conditions are satisfied, the pointer for s2 moves to the next character (incremented by 1).

The function accelerates the process by immediately moving forward in the search as soon as a suitable condition is met, ensuring efficient mapping through possible cyclic increments. It returns true if it's possible to resequence s2 into a subsequence of s1 following these incremental rules, indicated by traversing all characters in s2 (indexS2 == len2). Otherwise, it returns false indicating that s2 cannot be transformed into a valid subsequence of s1 under these conditions.

java 
class Solution {
    
    public boolean isSubsequencePossible(String s1, String s2) {
        int indexS2 = 0;
        int lenS1 = s1.length(), lenS2 = s2.length();
    
        for (
            int indexS1 = 0;
            indexS1 < lenS1 && indexS2 < lenS2;
            ++indexS1
        ) {
            if (
                s1.charAt(indexS1) == s2.charAt(indexS2) ||
                (s1.charAt(indexS1) + 1 == s2.charAt(indexS2)) ||
                (s1.charAt(indexS1) - 25 == s2.charAt(indexS2))
            ) {
                indexS2++;
            }
        }
        return indexS2 == lenS2;
    }
}

The Java function isSubsequencePossible(String s1, String s2) checks whether the string s2 can be made a subsequence of s1 via cyclic increments. A cyclic increment involves modifying a character by either incrementing it by one or treating 'z' as a cyclic increment to 'a'.

  • First, initialize an index for s2, indexS2, starting at zero.
  • Use the lengths of s1 and s2, denoted as lenS1 and lenS2, for determining loop termination.
  • Iterate through each character of s1. For each character of s1:
    • If the current character of s1 equals the corresponding character in s2 or represents a cyclic increment (either directly by one or cycling through from 'z' to 'a'), increment the s2 index indexS2 by one.
  • After the loop, determine if s2 is a subsequence by checking if indexS2 equals lenS2.

The method returns true if s2 can successfully be a subsequence of s1 under these constraints, false otherwise.

python 
class Solution:
    def isSubsequencePossible(self, sequence1: str, sequence2: str) -> bool:
        index_seq2 = 0
        len_seq1, len_seq2 = len(sequence1), len(sequence2)
    
        # Iterate over characters of sequence1
        for char_index in range(len_seq1):
            if index_seq2 < len_seq2 and (
                sequence1[char_index] == sequence2[index_seq2]
                or ord(sequence1[char_index]) + 1 == ord(sequence2[index_seq2])
                or ord(sequence1[char_index]) - 25 == ord(sequence2[index_seq2])
            ):
                # Increment index for sequence2 upon finding a matching condition
                index_seq2 += 1
    
        # If index_seq2 reached length of sequence2, all characters have been matched
        return index_seq2 == len_seq2

The provided code defines a Python class, Solution, which encompasses a method isSubsequencePossible to determine if one string (sequence1) can be transformed into a subsequence of another string (sequence2) through specific character modifications. The method employs cyclic increment logic, allowing character transformations by incrementing characters by 1 or wrapping from 'z' to 'a', to match characters in sequence2.

Implement the following steps to understand the provided functionality:

  1. Initialize an index (index_seq2) to keep track of the position in sequence2.
  2. Calculate the lengths of both input strings sequence1 and sequence2.
  3. Loop through each character in sequence1. Within this loop, check if the current character of sequence1 matches the corresponding character of sequence2 or can be transformed to do so by either incrementing by 1 or by cyclically incrementing 'z' to 'a'.
  4. If a match or valid transformation is found, advance the index_seq2 to check against the next character in sequence2.
  5. After the loop, determine if all characters of sequence2 have been matched by comparing if index_seq2 is equal to the length of sequence2.

The method returns True if sequence2 has been fully matched (i.e., it can be turned into a subsequence of sequence1 using the described transformations) and False otherwise. This solution supports checking sequences directly and transformation via specific cyclic character increments.

Comments

No comments yet.