If you’ve ever wondered why some solutions use dynamic programming while others go with a greedy scan, understanding subsequence in DSA will start to make those decisions click. That is what you are going to learn in-depth about in this article. Let us get started!<\/p>\n\n\n\n
TL;DR Summary<\/strong><\/h2>\n\n\n\n\n- What it is:<\/strong> a new sequence made by deleting zero or more elements while keeping the remaining order intact<\/li>\n\n\n\n
- Key rule:<\/strong> order is preserved, but elements don’t need to be contiguous, that’s what separates it from a substring<\/li>\n\n\n\n
- How many exist:<\/strong> a sequence of length n has 2^n possible subsequences, including the empty one<\/li>\n\n\n\n
- Where it matters most:<\/strong> LCS, LIS, DNA analysis, diff tools, and pattern matching<\/li>\n\n\n\n
- Time complexity to know:<\/strong> generating all subsequences is O(2^n); checking if one string is a subsequence of another is O(n+m)<\/li>\n<\/ul>\n\n\n\n
What is a Subsequence in DSA?<\/strong><\/h2>\n\n\n\n![\"What](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/10\/What-is-a-Subsequence_@2x-1200x630.webp\" "\\"\\"")
<\/figure>\n\n\n\nThink of a subsequence in DSA as a “filtered” version of a sequence where you keep the remaining elements in the same order. You simply pick some elements (possibly all or none) and delete the others, but never reorder the picks. Formally:<\/p>\n\n\n\n
\n- Definition:<\/strong> A subsequence in DSA is defined as: a new sequence obtained by deleting zero or more elements without changing the relative order<\/strong> of the remaining elements.<\/li>\n\n\n\n
- Example:<\/strong> Given the sequence \u27e8A,B,C,D,E,F\u27e9, one subsequence is \u27e8A,B,D\u27e9 (by deleting C, E, F). In strings, if your string is “ABCDE”, subsequences include “ACE”, “BD”, “ABCDE” (the whole string), and even the empty string “”. For instance, “geeks” has subsequences like “gks”, “ees”, “geeks” (itself), and “”<\/li>\n\n\n\n
- How to think about it:<\/strong> Imagine scanning through the original sequence and deciding for each element to either include<\/strong> it or skip<\/strong> it. Whatever you include (in order) becomes your subsequence. For example, if you start with “abcdef” and choose to keep a, c, e, you end up with the subsequence “ace”.<\/li>\n<\/ul>\n\n\n\n
Properties of Subsequence in DSA<\/strong><\/h2>\n\n\n\n![\"Properties](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/10\/Properties-of-Subsequences@2x-1200x630.webp\" "\\"\\"")
<\/figure>\n\n\n\nHere are some fundamental facts about a subsequence in DSA that often come up in Data Structures and Algorithms<\/a>:<\/p>\n\n\n\n\n- Self and Empty:<\/strong> Any sequence is trivially a subsequence of itself (keep all elements). Also, the empty<\/em> sequence (no elements) is a subsequence of every<\/strong> sequence (just delete everything).<\/li>\n\n\n\n
- Order Preserved:<\/strong> A subsequence must preserve original order. You cannot<\/strong> reorder elements; you can only drop them. For instance, from <A,B,A>, <A,A> is a valid subsequence (we kept the two A’s in order), but <A,A,B> is not (it changes the order).<\/li>\n\n\n\n
- Transitivity:<\/strong> If X is a subsequence of Y, and Y is a subsequence of Z, then X is a subsequence of Z (deletions compose).<\/li>\n\n\n\n
- Subsequence of Subsequence:<\/strong> If you take a subsequence and then take a subsequence of that, you still have a subsequence of the original<\/strong> sequence.<\/li>\n<\/ul>\n\n\n\n
These properties highlight that a subsequence in DSA is more general<\/strong> than substrings or subarrays (you can skip elements freely).<\/p>\n\n\n\nIf you want to read more about how DSA paves the way for effective coding and its use cases, consider reading HCL GUVI’s Free Ebook: The Complete Data Structures and Algorithms Handbook<\/a>.<\/p>\n\n\n\nIt covers the key concepts of Data Structures and Algorithms, including essential concepts, problem-solving techniques, and real MNC questions.<\/p>\n\n\n\n
Working with Subsequences: Algorithms and Code<\/strong><\/h2>\n\n\n\nIn practice, we often need to generate<\/strong> a subsequence in DSA problems, test<\/strong> subsequence relationships, or solve problems like LCS\/LIS. Below are some common algorithms and examples.<\/p>\n\n\n\n1. Generating All Instances of a Subsequence in DSA<\/h3>\n\n\n\n
One common task is to list all subsequences of a string or array. The straightforward method is a backtracking (pick\/don’t pick) recursion:<\/p>\n\n\n\n
\n- Idea:<\/strong> For each element of the sequence, you have two choices: include it in the current subsequence or skip it. Recurse on the next element with both choices.<\/li>\n<\/ul>\n\n\n\n
Example (<\/strong>Python code<\/strong><\/a>):<\/strong> The function below prints all subsequences of a string:<\/p>\n\n\n\ndef generate_subsequences(s, index=0, current=\"\"):\n if index == len(s):\n print(f\"'{current}'\")\n return\n # Include s[index] in the subsequence\n generate_subsequences(s, index+1, current + s[index])\n # Exclude s[index]\n generate_subsequences(s, index+1, current)\n\n# Example usage:\ngenerate_subsequences(\"ab\")\n\n# Actual output:\n# 'ab', 'a', 'b', ''<\/code><\/pre>\n\n\n\n\n- For input “ab”, this subsequence in DSA function prints ‘ab’, ‘a’, ‘b’, and ” (empty). The function always explores the “include” branch first, which is why the full string appears before the empty string in the output.<\/li>\n\n\n\n
- Explanation:<\/strong> In the above code, current accumulates the chosen characters. On reaching the end (index == len(s)), we have one complete subsequence. We backtrack by choosing not to include the current character as well.<\/li>\n\n\n\n
- Time Complexity:<\/strong> This method runs in O(2^n) time (and space) because it explores all subsequence combinations. It’s only practical for relatively small n<\/em>.<\/li>\n<\/ul>\n\n\n\n
2. Checking If One String is a Subsequence of Another<\/h3>\n\n\n\n
Another common problem in subsequence in DSA work is: given strings s1 and s2, check if s1 is a subsequence of s2. A classic linear-time solution uses two pointers:<\/p>\n\n\n\n
This is one of the most common subsequence in DSA interview questions.<\/p>\n\n\n\n
\n- Two-pointer approach:<\/strong> let i point into s1 (the smaller string) and j into s2 (the larger). Traverse s2 with j. Whenever s1[i] == s2[j], advance i. Always advance j. At the end, if i has reached the length of s1, all its characters were matched in order, so s1 is a subsequence. Otherwise, it’s not.<\/li>\n<\/ul>\n\n\n\n
Example (Python code):<\/strong><\/p>\n\n\n\ndef is_subsequence(small, large):\n i = 0\n for ch in large:\n if i < len(small) and small[i] == ch:\n i += 1\n return i == len(small)\n\n# Example usage:\nprint(is_subsequence(\"AXY\", \"ADXCPY\")) # True\nprint(is_subsequence(\"AXY\", \"YADXCP\")) # False<\/code><\/pre>\n\n\n\nThis example shows the two-pointer approach to a subsequence in DSA check in action.<\/p>\n\n\n\n
All characters of “AXY” appear in “ADXCPY” in order, so it returns True; in the second, although all characters exist, their order is broken, so it returns False.<\/p>\n\n\n\n
\n- Complexity:<\/strong> This runs in O(n+m) time (where n,m are string lengths) and O(1) extra space, which is optimal for this check.<\/li>\n<\/ul>\n\n\n\n
3. Longest Increasing Subsequence (LIS): A Classic Subsequence in DSA Problem<\/h3>\n\n\n\n
The Longest Increasing Subsequence<\/strong> problem finds a subsequence of a sequence of numbers that is strictly increasing and as long as possible. For example, in the array [3, 10, 2, 1, 20], the LIS is [3, 10, 20] of length 3.<\/p>\n\n\n\nA simple DP solution for this subsequence in DSA problem (length O(n^2)) is:<\/p>\n\n\n\n
def LIS_length(arr):\n n = len(arr)\n dp = [1]*n # dp[i] = length of LIS ending at i\n for i in range(n):\n for j in range(i):\n if arr[j] < arr[i]:\n dp[i] = max(dp[i], dp[j] + 1)\n return max(dp) if arr else 0<\/code><\/pre>\n\n\n\nFor [3, 10, 2, 1, 20], this subsequence in DSA solution would compute dp = [1,2,1,1,3] and return 3. (There are more efficient O(n log n) solutions, but the DP idea is straightforward.)<\/p>\n\n\n\n
4. Longest Common Subsequence (LCS): A Worked Example<\/h3>\n\n\n\n
LCS comes up so often in this article, and in real interviews, that it’s worth seeing the actual code, not just the definition. Given two strings, LCS finds the longest sequence that appears as a subsequence in both<\/em> of them.<\/p>\n\n\n\ndef LCS_length(s1, s2):\n m, n = len(s1), len(s2)\n dp = [[0] * (n + 1) for _ in range(m + 1)]\n for i in range(1, m + 1):\n for j in range(1, n + 1):\n if s1[i-1] == s2[j-1]:\n dp[i][j] = dp[i-1][j-1] + 1\n else:\n dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n return dp[m][n]\n\n# Example usage:\nprint(LCS_length(\"ABCBDAB\", \"BDCABA\")) # 4\nprint(LCS_length(\"AGGTAB\", \"GXTXAYB\")) # 4<\/code><\/pre>\n\n\n\nExplanation:<\/strong> dp[i][j] holds the LCS length using the first i characters of s1 and the first j characters of s2. If the current characters match, extend the previous diagonal result by one. If they don’t match, take whichever direction (skipping a character from either string) gives the longer result.<\/p>\n\n\n\nComplexity:<\/strong> this runs in O(m\u00d7n) time and space, a big improvement over trying every possible subsequence combination, which would take exponential time.<\/p>\n\n\n\nSubsequence vs Substring<\/strong><\/h2>\n\n\n\nIt’s important to distinguish a subsequence in DSA from substrings (or subarrays). The key difference is contiguity<\/strong>.<\/p>\n\n\n\n
What is a Subsequence in DSA?<\/strong><\/h2>\n\n\n\n<\/figure>\n\n\n\nThink of a subsequence in DSA as a “filtered” version of a sequence where you keep the remaining elements in the same order. You simply pick some elements (possibly all or none) and delete the others, but never reorder the picks. Formally:<\/p>\n\n\n\n
\n- Definition:<\/strong> A subsequence in DSA is defined as: a new sequence obtained by deleting zero or more elements without changing the relative order<\/strong> of the remaining elements.<\/li>\n\n\n\n
- Example:<\/strong> Given the sequence \u27e8A,B,C,D,E,F\u27e9, one subsequence is \u27e8A,B,D\u27e9 (by deleting C, E, F). In strings, if your string is “ABCDE”, subsequences include “ACE”, “BD”, “ABCDE” (the whole string), and even the empty string “”. For instance, “geeks” has subsequences like “gks”, “ees”, “geeks” (itself), and “”<\/li>\n\n\n\n
- How to think about it:<\/strong> Imagine scanning through the original sequence and deciding for each element to either include<\/strong> it or skip<\/strong> it. Whatever you include (in order) becomes your subsequence. For example, if you start with “abcdef” and choose to keep a, c, e, you end up with the subsequence “ace”.<\/li>\n<\/ul>\n\n\n\n
Properties of Subsequence in DSA<\/strong><\/h2>\n\n\n\n<\/figure>\n\n\n\nHere are some fundamental facts about a subsequence in DSA that often come up in Data Structures and Algorithms<\/a>:<\/p>\n\n\n\n\n- Self and Empty:<\/strong> Any sequence is trivially a subsequence of itself (keep all elements). Also, the empty<\/em> sequence (no elements) is a subsequence of every<\/strong> sequence (just delete everything).<\/li>\n\n\n\n
- Order Preserved:<\/strong> A subsequence must preserve original order. You cannot<\/strong> reorder elements; you can only drop them. For instance, from <A,B,A>, <A,A> is a valid subsequence (we kept the two A’s in order), but <A,A,B> is not (it changes the order).<\/li>\n\n\n\n
- Transitivity:<\/strong> If X is a subsequence of Y, and Y is a subsequence of Z, then X is a subsequence of Z (deletions compose).<\/li>\n\n\n\n
- Subsequence of Subsequence:<\/strong> If you take a subsequence and then take a subsequence of that, you still have a subsequence of the original<\/strong> sequence.<\/li>\n<\/ul>\n\n\n\n
These properties highlight that a subsequence in DSA is more general<\/strong> than substrings or subarrays (you can skip elements freely).<\/p>\n\n\n\nIf you want to read more about how DSA paves the way for effective coding and its use cases, consider reading HCL GUVI’s Free Ebook: The Complete Data Structures and Algorithms Handbook<\/a>.<\/p>\n\n\n\nIt covers the key concepts of Data Structures and Algorithms, including essential concepts, problem-solving techniques, and real MNC questions.<\/p>\n\n\n\n
Working with Subsequences: Algorithms and Code<\/strong><\/h2>\n\n\n\nIn practice, we often need to generate<\/strong> a subsequence in DSA problems, test<\/strong> subsequence relationships, or solve problems like LCS\/LIS. Below are some common algorithms and examples.<\/p>\n\n\n\n1. Generating All Instances of a Subsequence in DSA<\/h3>\n\n\n\n
One common task is to list all subsequences of a string or array. The straightforward method is a backtracking (pick\/don’t pick) recursion:<\/p>\n\n\n\n
\n- Idea:<\/strong> For each element of the sequence, you have two choices: include it in the current subsequence or skip it. Recurse on the next element with both choices.<\/li>\n<\/ul>\n\n\n\n
Example (<\/strong>Python code<\/strong><\/a>):<\/strong> The function below prints all subsequences of a string:<\/p>\n\n\n\ndef generate_subsequences(s, index=0, current=\"\"):\n if index == len(s):\n print(f\"'{current}'\")\n return\n # Include s[index] in the subsequence\n generate_subsequences(s, index+1, current + s[index])\n # Exclude s[index]\n generate_subsequences(s, index+1, current)\n\n# Example usage:\ngenerate_subsequences(\"ab\")\n\n# Actual output:\n# 'ab', 'a', 'b', ''<\/code><\/pre>\n\n\n\n\n- For input “ab”, this subsequence in DSA function prints ‘ab’, ‘a’, ‘b’, and ” (empty). The function always explores the “include” branch first, which is why the full string appears before the empty string in the output.<\/li>\n\n\n\n
- Explanation:<\/strong> In the above code, current accumulates the chosen characters. On reaching the end (index == len(s)), we have one complete subsequence. We backtrack by choosing not to include the current character as well.<\/li>\n\n\n\n
- Time Complexity:<\/strong> This method runs in O(2^n) time (and space) because it explores all subsequence combinations. It’s only practical for relatively small n<\/em>.<\/li>\n<\/ul>\n\n\n\n
2. Checking If One String is a Subsequence of Another<\/h3>\n\n\n\n
Another common problem in subsequence in DSA work is: given strings s1 and s2, check if s1 is a subsequence of s2. A classic linear-time solution uses two pointers:<\/p>\n\n\n\n
This is one of the most common subsequence in DSA interview questions.<\/p>\n\n\n\n
\n- Two-pointer approach:<\/strong> let i point into s1 (the smaller string) and j into s2 (the larger). Traverse s2 with j. Whenever s1[i] == s2[j], advance i. Always advance j. At the end, if i has reached the length of s1, all its characters were matched in order, so s1 is a subsequence. Otherwise, it’s not.<\/li>\n<\/ul>\n\n\n\n
Example (Python code):<\/strong><\/p>\n\n\n\ndef is_subsequence(small, large):\n i = 0\n for ch in large:\n if i < len(small) and small[i] == ch:\n i += 1\n return i == len(small)\n\n# Example usage:\nprint(is_subsequence(\"AXY\", \"ADXCPY\")) # True\nprint(is_subsequence(\"AXY\", \"YADXCP\")) # False<\/code><\/pre>\n\n\n\nThis example shows the two-pointer approach to a subsequence in DSA check in action.<\/p>\n\n\n\n
All characters of “AXY” appear in “ADXCPY” in order, so it returns True; in the second, although all characters exist, their order is broken, so it returns False.<\/p>\n\n\n\n
\n- Complexity:<\/strong> This runs in O(n+m) time (where n,m are string lengths) and O(1) extra space, which is optimal for this check.<\/li>\n<\/ul>\n\n\n\n
3. Longest Increasing Subsequence (LIS): A Classic Subsequence in DSA Problem<\/h3>\n\n\n\n
The Longest Increasing Subsequence<\/strong> problem finds a subsequence of a sequence of numbers that is strictly increasing and as long as possible. For example, in the array [3, 10, 2, 1, 20], the LIS is [3, 10, 20] of length 3.<\/p>\n\n\n\nA simple DP solution for this subsequence in DSA problem (length O(n^2)) is:<\/p>\n\n\n\n
def LIS_length(arr):\n n = len(arr)\n dp = [1]*n # dp[i] = length of LIS ending at i\n for i in range(n):\n for j in range(i):\n if arr[j] < arr[i]:\n dp[i] = max(dp[i], dp[j] + 1)\n return max(dp) if arr else 0<\/code><\/pre>\n\n\n\nFor [3, 10, 2, 1, 20], this subsequence in DSA solution would compute dp = [1,2,1,1,3] and return 3. (There are more efficient O(n log n) solutions, but the DP idea is straightforward.)<\/p>\n\n\n\n
4. Longest Common Subsequence (LCS): A Worked Example<\/h3>\n\n\n\n
LCS comes up so often in this article, and in real interviews, that it’s worth seeing the actual code, not just the definition. Given two strings, LCS finds the longest sequence that appears as a subsequence in both<\/em> of them.<\/p>\n\n\n\ndef LCS_length(s1, s2):\n m, n = len(s1), len(s2)\n dp = [[0] * (n + 1) for _ in range(m + 1)]\n for i in range(1, m + 1):\n for j in range(1, n + 1):\n if s1[i-1] == s2[j-1]:\n dp[i][j] = dp[i-1][j-1] + 1\n else:\n dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n return dp[m][n]\n\n# Example usage:\nprint(LCS_length(\"ABCBDAB\", \"BDCABA\")) # 4\nprint(LCS_length(\"AGGTAB\", \"GXTXAYB\")) # 4<\/code><\/pre>\n\n\n\nExplanation:<\/strong> dp[i][j] holds the LCS length using the first i characters of s1 and the first j characters of s2. If the current characters match, extend the previous diagonal result by one. If they don’t match, take whichever direction (skipping a character from either string) gives the longer result.<\/p>\n\n\n\nComplexity:<\/strong> this runs in O(m\u00d7n) time and space, a big improvement over trying every possible subsequence combination, which would take exponential time.<\/p>\n\n\n\nSubsequence vs Substring<\/strong><\/h2>\n\n\n\nIt’s important to distinguish a subsequence in DSA from substrings (or subarrays). The key difference is contiguity<\/strong>.<\/p>\n\n\n\n
<\/figure>\n\n\n\nThink of a subsequence in DSA as a “filtered” version of a sequence where you keep the remaining elements in the same order. You simply pick some elements (possibly all or none) and delete the others, but never reorder the picks. Formally:<\/p>\n\n\n\n
- \n
- Definition:<\/strong> A subsequence in DSA is defined as: a new sequence obtained by deleting zero or more elements without changing the relative order<\/strong> of the remaining elements.<\/li>\n\n\n\n
- Example:<\/strong> Given the sequence \u27e8A,B,C,D,E,F\u27e9, one subsequence is \u27e8A,B,D\u27e9 (by deleting C, E, F). In strings, if your string is “ABCDE”, subsequences include “ACE”, “BD”, “ABCDE” (the whole string), and even the empty string “”. For instance, “geeks” has subsequences like “gks”, “ees”, “geeks” (itself), and “”<\/li>\n\n\n\n
- How to think about it:<\/strong> Imagine scanning through the original sequence and deciding for each element to either include<\/strong> it or skip<\/strong> it. Whatever you include (in order) becomes your subsequence. For example, if you start with “abcdef” and choose to keep a, c, e, you end up with the subsequence “ace”.<\/li>\n<\/ul>\n\n\n\n
Properties of Subsequence in DSA<\/strong><\/h2>\n\n\n\n
<\/figure>\n\n\n\nHere are some fundamental facts about a subsequence in DSA that often come up in Data Structures and Algorithms<\/a>:<\/p>\n\n\n\n
- \n
- Self and Empty:<\/strong> Any sequence is trivially a subsequence of itself (keep all elements). Also, the empty<\/em> sequence (no elements) is a subsequence of every<\/strong> sequence (just delete everything).<\/li>\n\n\n\n
- Order Preserved:<\/strong> A subsequence must preserve original order. You cannot<\/strong> reorder elements; you can only drop them. For instance, from <A,B,A>, <A,A> is a valid subsequence (we kept the two A’s in order), but <A,A,B> is not (it changes the order).<\/li>\n\n\n\n
- Transitivity:<\/strong> If X is a subsequence of Y, and Y is a subsequence of Z, then X is a subsequence of Z (deletions compose).<\/li>\n\n\n\n
- Subsequence of Subsequence:<\/strong> If you take a subsequence and then take a subsequence of that, you still have a subsequence of the original<\/strong> sequence.<\/li>\n<\/ul>\n\n\n\n
These properties highlight that a subsequence in DSA is more general<\/strong> than substrings or subarrays (you can skip elements freely).<\/p>\n\n\n\n
If you want to read more about how DSA paves the way for effective coding and its use cases, consider reading HCL GUVI’s Free Ebook: The Complete Data Structures and Algorithms Handbook<\/a>.<\/p>\n\n\n\n
It covers the key concepts of Data Structures and Algorithms, including essential concepts, problem-solving techniques, and real MNC questions.<\/p>\n\n\n\n
Working with Subsequences: Algorithms and Code<\/strong><\/h2>\n\n\n\n
In practice, we often need to generate<\/strong> a subsequence in DSA problems, test<\/strong> subsequence relationships, or solve problems like LCS\/LIS. Below are some common algorithms and examples.<\/p>\n\n\n\n
1. Generating All Instances of a Subsequence in DSA<\/h3>\n\n\n\n
One common task is to list all subsequences of a string or array. The straightforward method is a backtracking (pick\/don’t pick) recursion:<\/p>\n\n\n\n
- \n
- Idea:<\/strong> For each element of the sequence, you have two choices: include it in the current subsequence or skip it. Recurse on the next element with both choices.<\/li>\n<\/ul>\n\n\n\n
Example (<\/strong>Python code<\/strong><\/a>):<\/strong> The function below prints all subsequences of a string:<\/p>\n\n\n\n
def generate_subsequences(s, index=0, current=\"\"):\n if index == len(s):\n print(f\"'{current}'\")\n return\n # Include s[index] in the subsequence\n generate_subsequences(s, index+1, current + s[index])\n # Exclude s[index]\n generate_subsequences(s, index+1, current)\n\n# Example usage:\ngenerate_subsequences(\"ab\")\n\n# Actual output:\n# 'ab', 'a', 'b', ''<\/code><\/pre>\n\n\n\n- \n
- For input “ab”, this subsequence in DSA function prints ‘ab’, ‘a’, ‘b’, and ” (empty). The function always explores the “include” branch first, which is why the full string appears before the empty string in the output.<\/li>\n\n\n\n
- Explanation:<\/strong> In the above code, current accumulates the chosen characters. On reaching the end (index == len(s)), we have one complete subsequence. We backtrack by choosing not to include the current character as well.<\/li>\n\n\n\n
- Time Complexity:<\/strong> This method runs in O(2^n) time (and space) because it explores all subsequence combinations. It’s only practical for relatively small n<\/em>.<\/li>\n<\/ul>\n\n\n\n
2. Checking If One String is a Subsequence of Another<\/h3>\n\n\n\n
Another common problem in subsequence in DSA work is: given strings s1 and s2, check if s1 is a subsequence of s2. A classic linear-time solution uses two pointers:<\/p>\n\n\n\n
This is one of the most common subsequence in DSA interview questions.<\/p>\n\n\n\n
- \n
- Two-pointer approach:<\/strong> let i point into s1 (the smaller string) and j into s2 (the larger). Traverse s2 with j. Whenever s1[i] == s2[j], advance i. Always advance j. At the end, if i has reached the length of s1, all its characters were matched in order, so s1 is a subsequence. Otherwise, it’s not.<\/li>\n<\/ul>\n\n\n\n
Example (Python code):<\/strong><\/p>\n\n\n\n
def is_subsequence(small, large):\n i = 0\n for ch in large:\n if i < len(small) and small[i] == ch:\n i += 1\n return i == len(small)\n\n# Example usage:\nprint(is_subsequence(\"AXY\", \"ADXCPY\")) # True\nprint(is_subsequence(\"AXY\", \"YADXCP\")) # False<\/code><\/pre>\n\n\n\nThis example shows the two-pointer approach to a subsequence in DSA check in action.<\/p>\n\n\n\n
All characters of “AXY” appear in “ADXCPY” in order, so it returns True; in the second, although all characters exist, their order is broken, so it returns False.<\/p>\n\n\n\n
- \n
- Complexity:<\/strong> This runs in O(n+m) time (where n,m are string lengths) and O(1) extra space, which is optimal for this check.<\/li>\n<\/ul>\n\n\n\n
3. Longest Increasing Subsequence (LIS): A Classic Subsequence in DSA Problem<\/h3>\n\n\n\n
The Longest Increasing Subsequence<\/strong> problem finds a subsequence of a sequence of numbers that is strictly increasing and as long as possible. For example, in the array [3, 10, 2, 1, 20], the LIS is [3, 10, 20] of length 3.<\/p>\n\n\n\n
A simple DP solution for this subsequence in DSA problem (length O(n^2)) is:<\/p>\n\n\n\n
def LIS_length(arr):\n n = len(arr)\n dp = [1]*n # dp[i] = length of LIS ending at i\n for i in range(n):\n for j in range(i):\n if arr[j] < arr[i]:\n dp[i] = max(dp[i], dp[j] + 1)\n return max(dp) if arr else 0<\/code><\/pre>\n\n\n\nFor [3, 10, 2, 1, 20], this subsequence in DSA solution would compute dp = [1,2,1,1,3] and return 3. (There are more efficient O(n log n) solutions, but the DP idea is straightforward.)<\/p>\n\n\n\n
4. Longest Common Subsequence (LCS): A Worked Example<\/h3>\n\n\n\n
LCS comes up so often in this article, and in real interviews, that it’s worth seeing the actual code, not just the definition. Given two strings, LCS finds the longest sequence that appears as a subsequence in both<\/em> of them.<\/p>\n\n\n\n
def LCS_length(s1, s2):\n m, n = len(s1), len(s2)\n dp = [[0] * (n + 1) for _ in range(m + 1)]\n for i in range(1, m + 1):\n for j in range(1, n + 1):\n if s1[i-1] == s2[j-1]:\n dp[i][j] = dp[i-1][j-1] + 1\n else:\n dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n return dp[m][n]\n\n# Example usage:\nprint(LCS_length(\"ABCBDAB\", \"BDCABA\")) # 4\nprint(LCS_length(\"AGGTAB\", \"GXTXAYB\")) # 4<\/code><\/pre>\n\n\n\nExplanation:<\/strong> dp[i][j] holds the LCS length using the first i characters of s1 and the first j characters of s2. If the current characters match, extend the previous diagonal result by one. If they don’t match, take whichever direction (skipping a character from either string) gives the longer result.<\/p>\n\n\n\n
Complexity:<\/strong> this runs in O(m\u00d7n) time and space, a big improvement over trying every possible subsequence combination, which would take exponential time.<\/p>\n\n\n\n
Subsequence vs Substring<\/strong><\/h2>\n\n\n\n
It’s important to distinguish a subsequence in DSA from substrings (or subarrays). The key difference is contiguity<\/strong>.<\/p>\n\n\n\n
- Complexity:<\/strong> This runs in O(n+m) time (where n,m are string lengths) and O(1) extra space, which is optimal for this check.<\/li>\n<\/ul>\n\n\n\n
- Time Complexity:<\/strong> This method runs in O(2^n) time (and space) because it explores all subsequence combinations. It’s only practical for relatively small n<\/em>.<\/li>\n<\/ul>\n\n\n\n
- Order Preserved:<\/strong> A subsequence must preserve original order. You cannot<\/strong> reorder elements; you can only drop them. For instance, from <A,B,A>, <A,A> is a valid subsequence (we kept the two A’s in order), but <A,A,B> is not (it changes the order).<\/li>\n\n\n\n
- Example:<\/strong> Given the sequence \u27e8A,B,C,D,E,F\u27e9, one subsequence is \u27e8A,B,D\u27e9 (by deleting C, E, F). In strings, if your string is “ABCDE”, subsequences include “ACE”, “BD”, “ABCDE” (the whole string), and even the empty string “”. For instance, “geeks” has subsequences like “gks”, “ees”, “geeks” (itself), and “”<\/li>\n\n\n\n
![\"Applications](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/10\/Applications-of-Subsequences@2x-1200x630.webp\" "\\"\\"")
<\/figure>\n\n\n\n