Similar Problems
Similar Problems not available
Append Characters To String To Make Subsequence - Leetcode Solution
Companies:
LeetCode: Append Characters To String To Make Subsequence Leetcode Solution
Difficulty: Medium
Topics: greedy string two-pointers
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.
Append Characters To String To Make Subsequence Solution Code
1