Python Program To Check Subsequence Of Two Strings

Check if one string is a subsequence of another string by verifying all characters appear in the same order

Understand the Problem

Problem Statement

The program must accept two string values S1 and S2 as the input. The program must print Found if S2 is a subsequence of S1. Else the program must print NotFound as the output. The string S2 is said to be a subsequence of string S1 if all the characters of S2 are present in S1 in the same order.

Constraints

1 ≤ Length of S1 ≤ 10^5
1 ≤ Length of S2 ≤ 10^5
Both strings contain only lowercase alphabetic characters
Time complexity should be O(n + m) where n and m are lengths of S1 and S2
Space complexity should be O(1)

Examples

Example 1

Input

management
amet

Output

Found

Explanation

The characters 'a', 'm', 'e', 't' appear in the same order in 'management' (at positions 1, 2, 6, 7), so 'amet' is a valid subsequence.

Example 2

Input

telescope
lspc

Output

NotFound

Explanation

The character 'c' does not appear in 'telescope' after the character 'p', so 'lspc' cannot be a subsequence of 'telescope'.

Solution

#include <stdio.h>
#include <string.h>

int main() {
    char s1[100001], s2[100001];
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    
    // Remove newline characters
    s1[strcspn(s1, "\n")] = 0;
    s2[strcspn(s2, "\n")] = 0;
    
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int i = 0, j = 0;
    
    while (i < len1 && j < len2) {
        if (s1[i] == s2[j]) {
            i++;
            j++;
        } else {
            j++;
        }
    }
    
    if (i == len1) {
        printf("Found\n");
    } else {
        printf("NotFound\n");
    }
    
    return 0;
}

Time:O(n + m) where n is length of S1 and m is length of S2

Space:O(1) - only using a constant amount of extra space for pointers

Approach:

The C solution follows the same two-pointer approach. It reads both strings using fgets(), removes the newline characters, then uses a while loop to traverse through the strings. The pointer 'i' tracks position in S1 (the subsequence we're looking for), and 'j' tracks position in S2 (the string we're searching in). When characters match, both pointers advance; otherwise only j advances. The solution efficiently handles the large input constraints with O(1) space complexity.

Visual Explanation

Loading diagram...

All Problems