C++ String Exercises: Check if a string is a subsequence of another 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> // Input/output stream library
#include <algorithm> // Standard algorithm library for operations on sequences

using namespace std; // Using the standard namespace

// Function to check if 'subse' is a subsequence of 'word'
bool is_Subsequence(string subse, string word) {
    int j = 0; // Initialize index for 'word'
    for (int i = 0; i < subse.size(); i++) { // Loop through characters of 'subse'
        if (word[j] == subse[i]) // If characters match
            j++; // Move to the next character in 'word'
    }
    // Return true if all characters in 'subse' found in 'word' in order, else return false
    return (j == word.size()) ? true : false;
}

int main() {
    // Test cases
    string word1 = "apple";
    string subse1 = "apl";
    cout << "word1: " << word1;
    cout << "\nsubse1: " << subse1;
    cout << "\nIs subse1 the subsequence of word1? " << is_Subsequence(word1, subse1);

    string word2 = "apple";
    string subse2 = "ppe";
    cout << "\n\nword2: " << word2;
    cout << "\nsubse2: " << subse2;
    cout << "\nIs subse2 the subsequence of word2? " << is_Subsequence(word2, subse2);

    string word3 = "ACGGTGTCGTGCTATGCTGATGCTGACTTATATGCTA";
    string subse3 = "CGTTCGGCTATGCTTCTACTTATTCTA";
    cout << "\n\nword3: " << word3;
    cout << "\nsubse3: " << subse3;
    cout << "\nIs subse3 the subsequence of word3? " << is_Subsequence(word3, subse3);

    string word4 = "CGTTCGGCTATCGTACGTTCTATTCTATGATTTCTAA";
    string subse4 = "CGTTCGGCTATGCZTTCTACTTATTCTA";
    cout << "\n\nword4: " << word4;
    cout << "\nsubse4: " << subse4;
    cout << "\nIs subse4 the subsequence of word4? " << is_Subsequence(word4, subse4);

    return 0; // Return 0 to indicate successful completion
}

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 C++ Exercise: Length of the longest palindrome in a given string.