Greedy: Check if the string is a substring of another string

Problem Statement:

You are given 2 strings s, t.

You need to check if s is a substring of t.

A substring of a string is a new string that is formed by deleting some of the character without disturbing the relative position.

Example

Input: s = “abc”, t = “aerbrtcsd”
Output: true

Solution

We can use greedy, 2 pointer approach.

In this approach, we will start from the starting index of the string s, and check if the character is there in string t.

If we find that char, we move to the next char in string s and continue to search.

Then finally we will check if we got all the chars in the string s.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

bool isSubsequence(string s, string t) 
{
  int idx = 0;
  for (int i = 0; i < t.size(); i++) 
  {
      if (s[idx] == t[i]) {
          idx++;
      }
  }
  return idx == s.size();
}

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

   if(isSubsequence(s, t)){
      cout<<"It is a subsequence"<<endl;
   } else {
      cout<<"It is not a subsequence"<<endl;
   }
   return 0;
}

Output:

It is a subsequence