Is Subsequence

🏠 ⬅️ ➡️

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

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

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 <= 104
  • s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
⚠️ Correct 
program main
    implicit none

    character(len=:), allocatable :: s, t
    logical :: result

    ! Example 1
    s = 'abc'
    t = 'ahbgdc'
    result = is_subsequence(s, t)
    print '(L1)', result

    ! Example 2
    s = 'axc'
    t = 'ahbgdc'
    result = is_subsequence(s, t)
    print '(L1)', result

contains

    function is_subsequence(s, t) result(res)
        implicit none
        character(len=*), intent(in) :: s, t
        logical :: res
        integer :: i, j

        res = .false.
        do i = 1, len(t) - len(s) + 1
            do j = 1, len(s)
                if (s(j:j) /= t(i+j-1:i+j-1)) exit
            end do
            if (j == len(s)+1) then
                res = .true.
                exit
            end if
        end do
    end function is_subsequence

end program main
❌ Compiled
❌ Executed
❌ Correct 
! This program checks if a given string s is a subsequence of another given string t.
! A subsequence of a string is a new string formed by deleting some (can be none) of the characters
! without disturbing the relative positions of the remaining characters.

PROGRAM subsequence
  IMPLICIT NONE

  CHARACTER(len=100) :: s, t
  LOGICAL :: is_subsequence

CONTAINS

  SUBROUTINE check_subsequence(s, t, is_subsequence)
    IMPLICIT NONE
    CHARACTER(len=*), INTENT(IN) :: s, t
    LOGICAL, INTENT(OUT) :: is_subsequence

    INTEGER :: i, j

    is_subsequence = .FALSE.

    ! Check if s is a subsequence of t
    DO i = 1, len_trim(t) - len_trim(s) + 1
      DO j = 1, len_trim(s)
        IF (t(i+j-1:i+j-1) /= s(j:j)) EXIT
        IF (j == len_trim(s)) THEN
          is_subsequence = .TRUE.
          EXIT
        END IF
      END DO
    END DO

  END SUBROUTINE check_subsequence

END PROGRAM subsequence

! Test cases
PROGRAM test_subsequence
  IMPLICIT NONE

  CHARACTER(len=100) :: s, t
  LOGICAL :: is_subsequence

  ! Test case 1: s is a subsequence of t
  s = "abc"
  t = "ahbgdc"
  CALL check_subsequence(s, t, is_subsequence)
  IF (is_subsequence) THEN
    WRITE (*,*) "Test case 1: PASS"
  ELSE
    WRITE (*,*) "Test case 1: FAIL"
  END IF

  ! Test case 2: s is not a subsequence of t
  s = "axc"
  t = "ahbgdc"
  CALL check_subsequence(s, t, is_subsequence)
  IF (.NOT. is_subsequence) THEN
    WRITE (*,*) "Test case 2: PASS"
  ELSE
    WRITE (*,*) "Test case 2: FAIL"
  END IF

END PROGRAM test_subsequence
🌐 Data from online sources 
def is_subsequence(s, t):
    si, ti = 0, 0

    while si < len(s) and ti < len(t):
        if s[si] == t[ti]:
            si += 1
        ti += 1

    return si == len(s)

We use two pointers to iterate through the strings `s` and `t`. The `si` pointer will be used to iterate through the string `s` and the `ti` pointer will be used for `t`.

At each iteration of the loop, if the character at the current position of both strings is the same, we increment the si pointer. We will always increment the ti pointer.

The loop will continue until we have checked all the characters in the s string or until we have checked all the characters in the t string. If the si pointer is equal to the length of the s string, it means we've found all the characters in the t string and the function returns true. Otherwise, it returns false.

This algorithm runs with a time complexity of O(max(n, m)) where n and m are the lengths of the strings s and t, respectively.

🌐 Data from online sources 
bool isSubsequence(std::string s, std::string t) {
    int si = 0, ti = 0;

    while (si < s.size() && ti < t.size()) {
        if (s[si] == t[ti])
            si++;
        ti++;
    }

    return si == s.size();
}

We use two pointers to iterate through the strings `s` and `t`. The `si` pointer will be used to iterate through the string `s` and the `ti` pointer will be used for `t`.

At each iteration of the loop, if the character at the current position of both strings is the same, we increment the si pointer. We will always increment the ti pointer.

The loop will continue until we have checked all the characters in the s string or until we have checked all the characters in the t string. If the si pointer is equal to the length of the s string, it means we've found all the characters in the t string and the function returns true. Otherwise, it returns false.

This algorithm runs with a time complexity of O(max(n, m)) where n and m are the lengths of the strings s and t, respectively.