2825. Make String a Subsequence Using Cyclic Increments
Problem Description
The problem presented requires determining whether str2
can become a subsequence of str1
by performing a specific operation on str1
. The operation involves selecting a set of indices in str1
and incrementing the character at each index to the next character in a cyclic manner. This means that the alphabet is considered to be circular and incrementing 'z' would result in 'a'.
A subsequence is defined as a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. The goal is to verify if by applying the operation at most once, str2
can be made a subsequence of str1
.
Note that the problem specifies that the operation can be performed at most once, meaning you cannot perform this operation multiple times on str1
. The string str2
must either already be a subsequence of str1
or be one operation away from being a subsequence.
Intuition
The solution approach is based on the idea that for str2
to be a subsequence of str1
, each character in str2
must appear in str1
in the same order, with the possibility of characters in str2
being one cyclic increment away from the characters in str1
.
To implement this, iterate through each character in str1
and simulate the operation. For each character in str1
, determine what the next cyclic character would be ('z' to 'a', and any other character to its successor). If the current character in str1
, or its cyclic successor, matches the current character in str2
, then that means this character is in the correct position, or one operation away from it, to form a subsequence.
Using a pointer i
, keep track of the position in str2
that you are trying to match with str1
. Initialize this pointer to 0, and move it forward through str2
each time you find a match or a potential match after a cyclic increment in str1
.
If you reach the end of str2
by advancing this pointer throughout the iteration, it means that all characters in str2
are present in str1
in order or one operation away, and str2
is (or can become) a subsequence of str1
. If the pointer i
is equal to the length of str2
by the end of the iteration through str1
, return true
; otherwise, false
.
This approach allows checking whether str2
can be obtained by performing at most one operation on str1
, complying with the problem's constraints.
Learn more about Two Pointers patterns.
Solution Approach
The implementation of the solution in Python is straightforward and does not require the use of any complex data structures or patterns. It mainly utilizes basic control structures and string operations to achieve the goal.
Here is a step-by-step walk-through of the provided solution code:
-
A method
canMakeSubsequence
is defined in theSolution
class. It takes two parameters:str1
andstr2
(the input strings). -
An index variable
i
is initialized to0
. This variable is used to keep track of the current position instr2
that we are trying to match againststr1
. -
A
for
loop is used to iterate over each characterc
instr1
. -
Inside the loop, a new variable
d
is calculated. It contains the next character cyclically afterc
. Ifc
is 'z',d
would be 'a', otherwised
is the character that comes afterc
in the ASCII table, obtained bychr(ord(c) + 1)
. -
The loop checks if
i
is still within the bounds ofstr2
(i < len(str2)
), and if the current character ofstr2
(str2[i]
) matches either the current characterc
fromstr1
, or the next cyclic characterd
. Thein
operator checks membership within a tuple made ofc
andd
. -
If a match or potential match after a cyclic increment is found,
i
is incremented by1
, signifying that we have found the current character ofstr2
in thestr1
or one operation away from it. -
After the loop finishes, the algorithm checks whether
i
has advanced to the end ofstr2
by comparingi
with the length ofstr2
. If they are equal, it meansstr2
can be a subsequence ofstr1
after performing the operation at most once. Thus, it returnstrue
. -
If the end of
str2
has not been reached, it indicates thatstr2
cannot be made a subsequence ofstr1
with at most one operation, so the method returnsfalse
.
This solution is efficient because it requires only a single pass through str1
and stops as soon as all characters in str2
are accounted for. Since there are no additional data structures used, the space complexity is O(1), and the time complexity is O(n), where n is the length of str1
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example using str1 = "abcde"
and str2 = "axz"
. We want to determine whether we can transform str2
into a subsequence of str1
by performing the character increment operation at most once.
-
We begin with
i = 0
, which represents the position instr2
that we're looking to match instr1
. -
As we iterate through
str1
, we compare the characters instr2
with the characters instr1
and their cyclic successor. -
We start with the first character of
str1
, which isa
. We see thatstr2[i]
is alsoa
. Since they match, we can incrementi
to1
. -
We proceed to the second character in
str1
, which isb
. We check its cyclic successor, which isc
. Neither matchstr2[i]
, which is nowx
, so we don't incrementi
. -
We move to the third character in
str1
,c
. Its successor isd
, andstr2[i]
isx
. There's no match, so we leavei
unchanged. -
Next is
d
instr1
, with its successor beinge
.str2[i]
is stillx
. No match, soi
remains at1
. -
The final character in
str1
ise
, and its successor isf
(cyclic incrementing fromz
toa
, but regular increment otherwise). Yet again, there's no match withstr2[i]
, which remainsx
. -
We exit the loop and compare
i
with the length ofstr2
. We see thati
is still1
, but the length ofstr2
is3
. Sincei
does not equal the length ofstr2
, we cannot makestr2
a subsequence ofstr1
with at most one operation, and we returnfalse
.
In this example, the character x
in str2
cannot be matched in str1
since there is no character that can be incremented cyclically to x
in str1
. Therefore, str2
cannot become a subsequence of str1
with just one operation according to our given rules.
Solution Implementation
1class Solution:
2 def canMakeSubsequence(self, text: str, subsequence: str) -> bool:
3 index = 0 # Initialize a pointer for the position in subsequence
4
5 # Loop through each character in text
6 for character in text:
7 # Determine the next character after 'character' in alphabet, wrap around if it is 'z'
8 next_char = 'a' if character == 'z' else chr(ord(character) + 1)
9
10 # Check if the current pointer is within bounds of subsequence
11 if index < len(subsequence):
12 # If the current character in text is the same as the current character in subsequence
13 # Or if it is the next character in the alphabet, move the pointer in subsequence
14 if subsequence[index] in (character, next_char):
15 index += 1
16
17 # After the loop, if the pointer has reached the length of subsequence
18 # It means the subsequence can be formed, hence return True
19 return index == len(subsequence)
20
1class Solution {
2
3 /**
4 * Checks if str2 is a subsequence of str1 with the character replacement rule.
5 * Each character in str1 can remain the same or be replaced by the next
6 * character in alphabetical order to match a character in str2.
7 *
8 * @param str1 The string to be transformed.
9 * @param str2 The target subsequence.
10 * @return true if str2 is a subsequence of str1 after allowed transformations.
11 */
12 public boolean canMakeSubsequence(String str1, String str2) {
13 int currentIndex = 0; // Pointer into str2 to track our current progress.
14 int lengthOfStr2 = str2.length(); // Total length of str2.
15
16 // Iterate through each character of str1.
17 for (char currentChar : str1.toCharArray()) {
18 // Calculate the next character in the alphabetical order ('z' wraps to 'a').
19 char nextChar = currentChar == 'z' ? 'a' : (char) (currentChar + 1);
20
21 // Check if the current character in str1 matches the current or next valid character in str2.
22 if (currentIndex < lengthOfStr2 &&
23 (str2.charAt(currentIndex) == currentChar || str2.charAt(currentIndex) == nextChar)) {
24 currentIndex++; // Move to the next character in str2.
25 }
26 }
27
28 // str2 is a subsequence of str1 only if we have traversed its entire length.
29 return currentIndex == lengthOfStr2;
30 }
31}
32
1class Solution {
2public:
3 bool canMakeSubsequence(string s1, string s2) {
4 // Initialize the index for traversing s2
5 int index = 0;
6 // Get the length of s2 for boundary checks
7 int s2Length = s2.size();
8
9 // Iterate over each character in s1
10 for (char currentChar : s1) {
11 // Determine the next character in the alphabet, wrapping around if 'z' is reached
12 char nextChar = currentChar == 'z' ? 'a' : static_cast<char>(currentChar + 1);
13
14 // Check if the current character of s2 matches currentChar or nextChar
15 // and ensure we have not exceeded the bounds of s2
16 if (index < s2Length && (s2[index] == currentChar || s2[index] == nextChar)) {
17 // Move to next character in s2
18 ++index;
19 }
20 }
21
22 // Return true if we have traversed the whole s2, making it a subsequence
23 return index == s2Length;
24 }
25};
26
1function canMakeSubsequence(sourceString: string, targetString: string): boolean {
2 // Initialize a pointer to track the characters in targetString
3 let pointer = 0;
4
5 // Get the length of targetString for comparison
6 const targetLength = targetString.length;
7
8 // Loop through the characters of sourceString to check if a subsequence can be made
9 for (const sourceChar of sourceString) {
10
11 // Determine the character that follows sourceChar in the alphabet,
12 // wrapping around from 'z' to 'a'
13 const nextChar = sourceChar === 'z' ? 'a' : String.fromCharCode(sourceChar.charCodeAt(0) + 1);
14
15 // If the current character in the targetString matches sourceChar
16 // or the next character in the alphabetical sequence,
17 // increment the pointer to continue with the next character
18 if (pointer < targetLength && (targetString[pointer] === sourceChar || targetString[pointer] === nextChar)) {
19 pointer++;
20 }
21 }
22
23 // A subsequence can be made if the pointer has reached the end of targetString
24 return pointer === targetLength;
25}
26
Time and Space Complexity
The given Python code determines whether str2
can be formed as a subsequence of str1
by either taking a character as it is or replacing it with the next character in the alphabet (with 'z' converted to 'a').
Time Complexity
The time complexity of the code is determined by the single loop that iterates over the characters of str1
. For each character c
in str1
:
- A constant-time operation is done to find the next character
d
(except for 'z', which turns to 'a'). - A constant-time operation
in
is used to check ifstr2[i]
is one of the two characters(c, d)
.
Since these operations are constant time, and the loop runs for each character in str1
, the time complexity is O(n)
, where n
is the length of str1
.
Space Complexity
The space complexity of the code:
- It uses a fixed number of simple variables (
i
,c
,d
), which requireO(1)
space. - No additional data structures are allocated proportionally to the size of the input.
Thus, the overall space complexity of the code is O(1)
– constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.