# LeetCode: is subsequence C#

Posted on

Problem

https://leetcode.com/problems/is-subsequence/

Given a string s and a string t, check if s is subsequence of t.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

Example 1:

Input: s = “abc”, t = “ahbgdc”
Output: true
Example 2:

Input: s = “axc”, t = “ahbgdc”
Output: false

Constraints:

0 <= s.length <= 100
0 <= t.length <= 10^4
Both strings consists only of lowercase characters.

``````using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;

{
/// <summary>
/// https://leetcode.com/problems/is-subsequence/
/// </summary>
[TestClass]
public class IsSubsequenceTest
{
[TestMethod]
public void TestMethod1()
{
string s = "abc", t = "ahbgdc";
Assert.IsTrue(IsSubsequence(s, t));
Assert.IsTrue(IsSubsequence2(s, t));
}

[TestMethod]
public void TestMethod2()
{
string s = "axc", t = "ahbgdc";
Assert.IsFalse(IsSubsequence(s, t));
Assert.IsFalse(IsSubsequence2(s, t));
}

public bool IsSubsequence(string s, string t)
{
return Helper(s, t, 0, 0);
}

/// <summary>
/// if the letters are equal (letter is found) continue to the next letter of s
/// if the letter is not found in t continue to the next letter of t.
/// if you reached the end of s, then s is a subsequence  of t.
/// if you reach the end of t. then s is not a subsequence of t
/// </summary>
/// <param name="s"></param>
/// <param name="t"></param>
/// <param name="sIndex"></param>
/// <param name="tIndex"></param>
/// <returns></returns>
private bool Helper(string s, string t, int sIndex, int tIndex)
{
if (sIndex == s.Length)
{
return true;
}
if (tIndex == t.Length)
{
return false;
}
if (s[sIndex] == t[tIndex])
{
return Helper(s, t, sIndex + 1, tIndex + 1);
}
else
{
return Helper(s, t, sIndex, tIndex + 1);
}
}

public bool IsSubsequence2(string s, string t)
{
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(t))
{
return false;
}

Dictionary<char, List<int>> map = new Dictionary<char, List<int>>();

//pre-process t
for (int i = 0; i < t.Length; i++)
{
if (!map.ContainsKey(t[i]))
{
}

}

int prev = -1;
for (int i = 0; i < s.Length; i++)
{
if (!map.ContainsKey(s[i]))
{
return false;
}
else
{
var list = map[s[i]];
prev = BinarySearch(prev, list, 0, list.Count - 1);
if (prev == -1)
{
return false;
}

prev++;
}
}

return true;
}

private int BinarySearch(int prev, List<int> list, int start, int end)
{
while (start <= end)
{
int mid = (end - start) / 2 + start;
if (list[mid] < prev)
{
start = mid + 1;
}
else
{
end = mid - 1;
}
}

if (start == list.Count)
{
return -1;
}

return list[start];
}
}
}
``````

Solution

From a performance point of perspective, `IsSubsequence` will always be faster than `IsSubsequence2`, because it only needs to iterate 2 arrays simultaneously and has no further allocations on the heap.

If you want to improve on performance and also make sure, you never get a `StackOverFlowException`, you should get rid of the recursion in your `Helper` method and instead use a loop.

``````public static bool IsSubsequence3(string s, string t)
{
var sIndex = 0;
for (var tIndex = 0; tIndex < t.Length; tIndex++)
{
if (s[sIndex] == t[tIndex])
sIndex++;

if(sIndex == s.Length)
return true;
}

return false;
}
``````

When running a Debug build, using the input `string s = "abc", t = "ahbgdc";` and executing the Method more than 1,000,000 times, `IsSubsequence4` becomes faster. However when you run it in a Release build, the performance is the same, as compiler optimizations kick in and they will implicitly do what is written here explicitly (trade the property access for a local field).

``````public static bool IsSubsequence4(string s, string t)
{
var sIndex = 0;
var sLength = s.Length;
var tLength = t.Length;
for (var tIndex = 0; tIndex < tLength; tIndex++)
{
if (s[sIndex] == t[tIndex])
sIndex++;

if(sIndex == sLength)
return true;
}

return false;
}
``````

I also tried using `AsSpan()` and `ToCharArray()` and the strings to get rid of the `callvirt System.String.get_Chars` in the IL code and I tried using an Enumerator. Both where slower than `IsSubsequence3`

``````public static bool IsSubsequence5(string s, string t)
{
var sIndex = 0;
var sLength = s.Length;
var tLength = t.Length;
var sChars = s.AsSpan();
var tChars = t.AsSpan();
for (var tIndex = 0; tIndex < tLength; tIndex++)
{
if (sChars[sIndex] == tChars[tIndex])
sIndex++;

if(sIndex == sLength)
return true;
}

return false;
}
``````
``````public static bool IsSubsequence6(string s, string t)
{
using var sEnum = s.GetEnumerator();
sEnum.MoveNext();
using var tEnum = t.GetEnumerator();
while (tEnum.MoveNext())
{
if (sEnum.Current == tEnum.Current)
{
if(!sEnum.MoveNext())
return true;
}
}

return false;
}
``````