Subsequence meaning in DSA

A subsequence is defined as a sequence that can be derived from another string/sequence by deleting some or none of the elements without changing the order of the remaining elements.

For example: Let’s take “GeeksForGeeks”, GeeksF will be a subsequence of “GeeksForGeeks”.

Example of Subsequence

Properties of Subsequence:

• A sequence is a subsequence of itself.
• The empty sequence is a subsequence of every sequence.
• The number of possible subsequences of a sequence of length n is 2ⁿ.
• A subsequence of a subsequence is also a subsequence of the original sequence.
• The relative order of characters is unchanged.

How it is different from a Substring? 

• A substring is a sequence of consecutive characters of a larger string or sequence whereas, in a subsequence, the characters need not to be consecutive.
• The total possible number of substrings for a string of length n is (n*(n+1)/2) whereas the total number of possible subsequences is (2ⁿ).

To learn more about the differences, refer to this article.

Applications of Subsequence:

• DNA Sequence Analysis: Subsequence is basically a pattern recognition concept, which can be used to identify similar patterns within the DNA sequence and to find important motifs or functional regions.
• Natural Language Processing: This is done by identifying and extracting subsequences of words that match a given pattern. NLP is focused on making AI more natural to humans, which needs to extract pattern from a large dataset. 
• Speech Recognition: Subsequences are used in speech recognition to identify phonemes (the smallest units of sound in a language).
• Computer Vision: Subsequences are used in computer vision to recognize patterns in images or videos. For example, face lock in your mobile phones uses this feature to identify your face.
• Financial Analysis: Subsequences are used in financial analysis to identify patterns and trends in financial data, such as stock prices or sales figures. 

Advantages of Subsequence:

• Subsequences are more general than substrings because they can capture non-contiguous patterns.
• They can identify patterns that are more complex and have greater flexibility in capturing features of a sequence.

Disadvantages of Subsequence:

• Finding all possible subsequences of a given sequence can be computationally expensive, especially if the sequence is long.
• Algorithms that use subsequences may have high time and space complexity.

What else can you read?

• Subarray/Substring vs Subsequence and Programs to Generate them
• Print all subsequences of a string
• Check if a string is subsequence of another