Subsequence vs Substring

When working with strings, you may come across the terms "subsequence" and "substring." Although they sound similar, they have different meanings and use cases.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements, without changing the order of the remaining elements. For example, let's consider the string "algodaily". If we remove the letters "l", "g", and "y", we get the subsequence "aoday". Notice that the order of the remaining letters remains the same.

On the other hand, a substring is a contiguous sequence of characters within a string. In the same example, if we take the characters from index 3 to 5, we get the substring "day".

So, the key difference between a subsequence and a substring is that a subsequence can leave out characters and the order matters, while a substring must have contiguous characters with no gaps.

Now, let's see some code examples to understand the difference better:

1string str = "algodaily";
2string subsequence = "aday";
3string substring = "dayl";
4
5bool isSubsequence = IsSubsequence(str, subsequence);
6bool isSubstring = IsSubstring(str, substring);
7
8Console.WriteLine("Is subsequence: " + isSubsequence);
9Console.WriteLine("Is substring: " + isSubstring);
10
11bool IsSubsequence(string str, string subsequence)
12{
13    int subIdx = 0;
14    for (int i = 0; i < str.Length && subIdx < subsequence.Length; i++)
15    {
16        if (str[i] == subsequence[subIdx])
17        {
18            subIdx++;
19        }
20    }
21    return subIdx == subsequence.Length;
22}
23
24bool IsSubstring(string str, string substring)
25{
26    return str.Contains(substring);
27}

In the above code snippet, we have two functions: IsSubsequence and IsSubstring. The IsSubsequence function iterates through the characters of the str and checks if each character matches the corresponding character in the subsequence. If all the characters in the subsequence are found in the str in the same order, it returns true, indicating that the subsequence is present in the str. On the other hand, the IsSubstring function simply uses the Contains method of the str to check if the substring is present.

By understanding the difference between a subsequence and a substring, you'll be able to approach different string manipulation problems effectively and choose the appropriate technique based on the problem requirements.

xxxxxxxxxx

string str = "algodaily";

string subsequence = "aday";

string substring = "dayl";

​

bool isSubsequence = IsSubsequence(str, subsequence);

bool isSubstring = IsSubstring(str, substring);

​

Console.WriteLine("Is subsequence: " + isSubsequence);

Console.WriteLine("Is substring: " + isSubstring);

​

bool IsSubsequence(string str, string subsequence)

{

    int subIdx = 0;

    for (int i = 0; i < str.Length && subIdx < subsequence.Length; i++)

    {

        if (str[i] == subsequence[subIdx])

        {

            subIdx++;

        }

    }

    return subIdx == subsequence.Length;

}

​

bool IsSubstring(string str, string substring)

{

    return str.Contains(substring);

}