Check if a String is Subsequence of Other

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Check if string A is a subsequence of string B. Two-pointer scan.

Algorithm

1i=0 (pointer in A), j=0 (pointer in B). If B[j]==A[i]: i++. j++ always. If i reaches len(A): true.

Common Pitfalls

•Same as LC 392. O(n) greedy scan. A is subsequence of B if all chars of A found in order in B.

Check if a String is Subsequence of Other.java

Java

// Approach: Two-pointer approach. Advance pointer in string s whenever characters match.
// If s pointer reaches the end, s is a subsequence of t.
// Time: O(n) Space: O(1)
class Solution {
    public boolean isSubSeq(String s1, String s2) {
        int l = s1.length(), n = s2.length(), i = 0, j = 0;
        while (j < n && i < l) {
            if (s1.charAt(i) == s2.charAt(j))
                i++;
            j++;
        }

        if (i == l)
            return true;
        return false;
    }
};

Was this solution helpful?