Is Subsequence Leetcode Solution

Problem Statement

In this problem, we are given two different strings. The goal is to find out whether the first string is a subsequence of the second.

Examples

first string = "abc"
second string = "mnagbcd"

true

first string = "burger"
second string = "dominos"

false

Approach(Recursive)

This is easy to see that we can start matching the strings from their ends. If the characters at the last of the strings match, then we have a reduced sub-problem of finding whether the two strings that can be obtained from the original ones after dropping their last characters follow the subsequence criteria. If the end characters do not match, we only drop the last character of the second string to search ahead in it.

This can be done recursively by passing the indices of the strings as parameters to compare the characters at every recursive call.

Algorithm

1. Index i denotes the last index of the first string and j denotes the last index of the second string in recursive calls
2. If i == -1:
   1. We have completely traversed the first string, return true
3. If j == -1:
   1. We have completely traversed the first string, return false
4. If first_string[i] == second_string[j]:
   1. call recursive functions with indices (i – 1 , j – 1)
5. Return the result of recursive function with indices (i , j – 1)

Implementation of Is Subsequence Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

string S , T;

bool checkSubsequence(int i , int j)
{
    if(i == -1)
        return true;
    if(j == -1)
        return false;
    if(S[i] == T[j])
        return checkSubsequence(i - 1 , j - 1);
    return checkSubsequence(i , j - 1);
}

bool isSubsequence(string s, string t)
{
    S = s , T = t;
    return checkSubsequence((int)s.size() - 1 , (int)t.size() - 1);
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

Java Program

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean checkSubsequence(int i , int j)
    {
        if(i == -1)
            return true;
        if(j == -1)
            return false;
        if(S.charAt(i) == T.charAt(j))
            return checkSubsequence(i - 1 , j - 1);
        return checkSubsequence(i , j - 1);
    }

    static boolean isSubsequence(String s, String t)
    {
        S = s;
        T = t;
        return checkSubsequence((int)s.length() - 1 , (int)t.length() - 1);
    }
}

true

Complexity Analysis of Is Subsequence Leetcode Solution

Time Complexity

O(min(N, M)) as we need to recur until either of the strings is traversed. N and M are the lengths of strings.

Space Complexity

O(min(M , N) in the worst case due to recursive calls.

Approach(Two-Pointers)

We can use the above technique, iteratively by maintaining two pointers i and j to store the last indices of respective strings. We can iterate until either of them becomes zero. If i (pointer of the first string) is greater than or equal to 0, we have not been able to traverse the first string completely, and hence, it is not a subsequence of the second. Else, we return true.

Algorithm

1. Initialize two pointers i and j storing the last indices of both the strings.
2. While i >= 0 and j >= 0:
   1. If first_string[i] == second_string[j]:
      1. i— , j—
   2. Else
      1. j—
3. If i >= 0:
   1. Return false
4. Return true

Implementation of Is Subsequence Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

string S , T;

bool isSubsequence(string s , string t)
{
    int i = s.size() , j = t.size();

    i-- , j--;

    while(i >= 0 && j >= 0)
    {
        if(s[i] == t[j])
            i-- , j--;
        else
            j--;
    }

    if(i >= 0)
        return false;
    return true;
}

int main()
{
    string s = "abc";
    string t = "mnagbcd";

    cout << (isSubsequence(s , t) ? "true" : "false") << '\n';
    return 0;
}

Java Program

class is_subsequence
{
    static String S , T;

    public static void main(String args[])
    {
        String a = "abc" , b = "mnagbcd";
        System.out.println((isSubsequence(a , b) ? "true" : "false"));
    }

    static boolean isSubsequence(String s , String t)
    {
        int i = s.length() , j = t.length();

        i--;
        j--;

        while(i >= 0 && j >= 0)
        {
            if(s.charAt(i) == t.charAt(j))
            {
                i--;
                j--;
            }
            else
                j--;
        }

        if(i >= 0)
            return false;
        return true;
    }
}

true

Complexity Analysis of Is Subsequence Leetcode Solution

Time Complexity

O(min(M , N)) as we keep iterating until i or j becomes zero. M and N are the lengths of the strings.

Space Complexity

O(1) as we use constant space in the memory.