Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
O(n)
if n is the length of t. O(1)
Run through a set of example cases:
HAPPY CASE
Input: s = "abc", t = "ahbgdc"
Output: true
Input: s = "axc", t = "ahbgdc"
Output: false
EDGE CASE
Input: "", ""
Output: true
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Strings, common solution patterns include:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Identify each s
character in string t in relative order. We will progress through string 's' if it exist in linear order in string 't'. If we get to the end of string 's', we verified that 's' is substring of 't', otherwise it is not.
1) Create two pointers to represent the character progression of string 's' and 't'
2) While pointerS is less than length of string 's' and pointerT is less than length of string 't'
a) Let's progress the pointerS every time we match with pointerT.
b) Let's progress pointerT everytime so we can get the next character.
3) Return whether or not we reached the end of string 's' by matching pointerS to length of string 's'.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
# Create two pointers to represent the character progression of string 's' and 't'
pointerS = pointerT = 0
# While pointerS is less than length of string 's' and pointerT is less than length of string 't'
while pointerS < len(s) and pointerT < len(t):
# Let's progress the pointerS every time we match with pointerT
if s[pointerS] == t[pointerT]:
pointerS += 1
# Let's progress pointerT everytime so we can get the next character
pointerT += 1
# Return whether or not we reached the end of string 's' by matching pointerS to length of string 's'
return pointerS == len(s)
class Solution {
public boolean isSubsequence(String s, String t) {
// Create two pointers to represent the character progression of string 's' and 't'
int i = 0, j = 0;
// While pointerS is less than length of string 's' and pointerT is less than length of string 't'
while(i < s.length() && j < t.length()){
// Let's progress the pointerS every time we match with pointerT
if(s.charAt(i) == t.charAt(j)) i++;
// Let's progress pointerT everytime so we can get the next character
j++;
}
// Return whether or not we reached the end of string 's' by matching pointerS to length of string 's'
return i == s.length();
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of characters in the string 's' and M
represents the number of characters in the string 't'.
O(M)
, because we only need to progress through all the characters in string 't' to verify if string 's' is a subsequence of string 't'.O(1)
, because we used two pointers which has a constant space cost.