Append Characters To String To Make Subsequence - Leetcode Solution

The problem statement is as follows:

Given two strings s and t, return true if t is a subsequence of s, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

To solve this problem, we need to iterate through the characters of both the strings and check if the characters of t are present in s in the order they appear in t. If all the characters of t are found in s, in the order they appear in t, then t is a subsequence of s.

In order to achieve the above approach, we can create two pointers i and j, initially pointing to the starting index of both strings s and t. We can then iterate through both the strings together and check for each character in t if it is present in s, starting from the current index of s until the end of s.

If a character in t is found in s, we can increment both i and j by 1, to check for the next character in t. If all the characters of t are found in s, in the order they appear in t, then t is a subsequence of s, and we can return true.

If at any point, we reach the end of s or t, we can break out of the loop and return false, as there are no more characters left to check for.

Code:

Here is the solution in Python:

def isSubsequence(self, s: str, t: str) -> bool:
    i = 0
    j = 0
    
    while i < len(s) and j < len(t):
        if t[j] == s[i]:
            j += 1
        i += 1
        
    if j == len(t):
        return True
    else:
        return False

Time Complexity : O(n) Space Complexity : O(1)

Explanation:

In this code, we are comparing two strings s and t to find out if t is a subsequence of s. We have taken two pointers, initially pointing to the starting index of both s and t and ran a while loop to look for the characters of t in s in the order they appear in t.

While iterating through the loop, if we find the current character of t in s, we increment the index of t by 1 to look for the next character, and if not found, then we increment the index of s by 1 to look for the next character. Once we have iterated through both strings and found all the characters of t in s in the order they appeared in t, we return True, otherwise, we return False.

1