C++ Exercises: Check whether a given string is a subsequence of another given string

C++ String: Exercise-21 with Solution

Write a C++ program to check whether a given string is a subsequence of another given string. Return 1 for true and 0 for false.

From Wikipedia,
In mathematics, a subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. For example, the sequence (A,B,D) is a subsequence of (A,B,C,D,E,F) obtained after removal of elements C, E and F. The relation of one sequence being the subsequence of another is a pre order.
Subsequences can contain consecutive elements, which were not consecutive in the original sequence. A subsequence which consists of a consecutive run of elements from the original sequence, such as (B,C,D) from (A,B,C,D,E,F) is a substring. The substring is a refinement of the subsequence.
The list of all subsequences for the word "apple" would be "a", "ap", "al", "ae", "app", "apl", "ape", "ale", "appl", "appe", "aple", "apple", "p", "pp", "pl", "pe", "ppl", "ppe", "ple", "pple", "l", "le", "e", "" (empty string).

Example-1:

Input: word = ‘apple’; subsequence = ‘apl’;

Output:

Example-2:

Input: word = ‘apple’; subsequence = ‘ppe’;

Output:

Example-3:

Input: word = ‘ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA’;
subsequence = ‘CGTTCGGCTATGCTTCTACTTATTCTA’;

Output:

Example-4:

Input: word = ’CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA’
subsequence = ‘CGTTCGGCTATGCZTTCTACTTATTCTA’;

Output:

Sample Solution:

C++ Code:

#include <iostream>

#include<algorithm>

using namespace std;
 
    bool is_Subsequence(string subse, string word) {
        int j=0;
        for(int i=0;i<subse.size();i++)
		{
            if(word[j]==subse[i])j++;
        }
      return (j==word.size())?true : false;
    }

int main()
{
 
  string word1 = "apple";
  string subse1 = "apl";
  cout << "word1: " << word1;
  cout << "\nsubse1: " << subse1;
  cout << "\nIs subse1 is the subsequence of word1? " << is_Subsequence(word1, subse1);
  string word2 = "apple";
  string subse2 = "ppe";
  cout << "\n\nword2: " << word2;
  cout << "\nsubse2: " << subse2;
  cout << "\nIs subse2 is the subsequence of word2? " << is_Subsequence(word2, subse2);
  string word3 = "ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA";
  string subse3 = "CGTTCGGCTATGCTTCTACTTATTCTA";
  cout << "\n\nword3: " << word3;
  cout << "\nsubse3: " << subse3;
  cout << "\nIs subse3 is the subsequence of word3? " << is_Subsequence(word3, subse3);
  string word4 = "CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA";
  string subse4 = "CGTTCGGCTATGCZTTCTACTTATTCTA";
  cout << "\n\nword4: " << word4;
  cout << "\nsubse4: " << subse4;
  cout << "\nIs subse4 is the subsequence of word4? " << is_Subsequence(word4, subse4);     
  return 0;    
}

Sample Output:

word1: apple
subse1: apl
Is subse1 is the subsequence of word1? 1

word2: apple
subse2: ppe
Is subse2 is the subsequence of word2? 1

word3: ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA
subse3: CGTTCGGCTATGCTTCTACTTATTCTA
Is subse3 is the subsequence of word3? 1

word4: CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA
subse4: CGTTCGGCTATGCZTTCTACTTATTCTA
Is subse4 is the subsequence of word4? 0

Flowchart:

C++ Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to find the length of the longest palindrome in a given string (uppercase or lowercase letters).