algoadvance

Leetcode 392. Is Subsequence

Problem Statement

Given two strings s and t, return true if s is a subsequence of t, 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).

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• Both s and t consist only of lowercase English letters.

Clarifying Questions

1. What should be returned if s is an empty string?
   • An empty string is considered a subsequence of any string, so the function should return true.
2. What if t is an empty string but s is not?
   • If t is empty and s is not, the function should return false.

Strategy

1. Use two pointers, one for each string, starting from the beginning.
2. Iterate through t using a pointer j.
3. For each character in t, if it matches the current character in s pointed by the pointer i, move the pointer i to the next character in s.
4. If pointer i reaches the end of s, this means all characters of s were found in sequence within t, hence return true.
5. If you finish iterating through t without i reaching the end of s, return false.

Code

public class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;

        int i = 0;
        for (int j = 0; j < t.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                if (i == s.length()) {
                    return true;
                }
            }
        }
        return false;
    }
}

Time Complexity

• Time Complexity: O(n), where n is the length of string t. We are iterating through t once.
• Space Complexity: O(1), as we are using only a constant amount of extra space for the pointers.

This ensures that the algorithm is efficient even with the maximum constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?