Elias Kirui

Ruby implementation:

def is_subsequence(s, t)
  i, j = 0, 0

  while i < s.length && j < t.length
    if s[i] == t[j]
      i += 1
    end
    j += 1
  end

  return i == s.length
end

This implementation uses two pointers, i for the string s and j for the string t. It iterates through both strings, and when a matching character is found, it increments the pointer for s. If i reaches the length of s, then s is a subsequence of t, and the function returns true. Otherwise, it returns false.

For the example s = "abc" and t = "ahbgdc", the output will be true because "abc" is a subsequence of "ahbgdc".

The time complexity is O(max(m, n)), where m is the length of string s and n is the length of string t. The while loop iterates through both strings until either one is fully traversed. In the worst case, it checks each character in both strings once.

The space complexity is O(1) since the algorithm uses a constant amount of extra space, regardless of the input size. The two pointers (i and j) and a few variables do not depend on the input size.

180

Is Subsequence