Check for Subsequence

Problem

Given two strings A and B, find if A is a subsequence of B.

Examples:

Example 1:

Input:
A = AXY 
B = YADXCP
Output: 0 
Explanation: A is not a subsequence of B as 'Y' appears before 'A'.

Example 2:

Input:
A = gksrek
B = geeksforgeeks
Output: 1
Explanation: A is a subsequence of B.

Your task:

You dont need to read input or print anything. Complete the function isSubSequence() which takes A and B as input parameters and returns a boolean value denoting if A is a subsequence of B or not.

• Expected Time Complexity: $O(N)$, where N is length of string B
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<= |A|,|B| <=10^4$

Solution

Python

def isSubSequence(self, A, B):
    n, m = len(A), len(B)
    i, j = 0, 0
    while (i < n and j < m):
        if (A[i] == B[j]):
            i += 1
        j += 1
    return i == n

Java

boolean isSubSequence(String A, String B){
    int n = A.length();
    int m = B.length();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (A.charAt(i) == B.charAt(j)) {
            i++;
        }
        j++;
    }
    return i == n;
}

C++

bool isSubSequence(string A, string B) {
    int n = A.length();
    int m = B.length();
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (A[i] == B[j]) {
            i++;
        }
        j++;
    }
    return i == n;
}

C

int isSubSequence(const char *A, const char *B) {
    int n = 0;  
    while (A[n] != '\0') {
        n++;
    }
    int m = 0;  
    while (B[m] != '\0') {
        m++;
    }
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (A[i] == B[j]) {
            i++;
        }
        j++;
    }
    return i == n;
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$