String Subsequence

Lessons Learned: Strings, For Loops

Given a string s, and a string t, check if s is a subsequence of t. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Examples:

  • isSubsequence(“xyz”, “abxcydz”) -> True (xyz is subsequence of abxcydz)

  • isSubsequence(“abc”, “xyacyb”) -> False (abc is not a subsequence of xyacyb)

  • isSubsequence(“seprp”, “sweprep”) -> True (seprp is a subsequence of sweprep)

The approach is quite simple - we loop through both strings, and if we find a match, we increment the counter on both strings. Otherwise, we just increment the counter only on string t.

Below is an iterative implementation of the above approach.

We’re done!