S1 Contains S2 In Python

Determine if the characters of string S2 appear in the same relative order within string S1

Understand the Problem

Problem Statement

Given two string values S1 and S2, determine if the characters of S2 occur in the same relative order within S1. The characters of S2 do not need to be continuous in S1, but they must maintain their relative order.

For example, if S1 is "superkoolfillerandcopperkit" and S2 is "skillrack", the output should be YES because all characters of "skillrack" appear in S1 in the correct order.

Constraints

1 ≤ Length of S1 ≤ 10^7
1 ≤ Length of S2 ≤ 10^7
Both strings contain only printable ASCII characters
Strings can be compared as case-sensitive

Examples

Example 1

Input

superkoolfillerandcopperkit
skillrack

Output

YES

Explanation

All characters of 'skillrack' appear in 'superkoolfillerandcopperkit' in the correct relative order: s(1), k(6), i(11), l(12), l(13), r(15), a(16), c(19), k(25).

Example 2

Input

germanactor
men

Output

NO

Explanation

The character 'n' appears before 'e' in 'germanactor', but in 'men', 'e' should come before 'n'. The relative order is not maintained.

Solution

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

int main() {
    char s1[10000001]; // Maximum length 10^7 + 1 for null terminator
    char s2[10000001];
    
    // Read both strings
    fgets(s1, sizeof(s1), stdin);
    fgets(s2, sizeof(s2), stdin);
    
    // Remove newline characters
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    
    if (s1[len1-1] == '\n') s1[len1-1] = '\0';
    if (s2[len2-1] == '\n') s2[len2-1] = '\0';
    
    len1 = strlen(s1);
    len2 = strlen(s2);
    
    // Two-pointer approach
    int i = 0, j = 0;
    
    while (i < len1 && j < len2) {
        if (s1[i] == s2[j]) {
            j++; // Found a match, move to next character in s2
        }
        i++; // Always move to next character in s1
    }
    
    // If we've matched all characters of s2
    if (j == len2) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    
    return 0;
}

Time:O(n) where n is the length of S1

Space:O(n + m) where n and m are lengths of S1 and S2

Approach:

The C solution implements the two-pointer approach:

Read both strings using fgets() to handle large inputs safely
Remove any trailing newlines from the input
Initialize two pointers: i for S1 and j for S2
Iterate through S1 (pointer i) and whenever we find a match with current S2 character (pointer j), increment j
If j reaches the end of S2, all characters were found in order
Print YES if all characters matched, NO otherwise

The algorithm is efficient with O(n) time complexity where n is the length of S1.

Visual Explanation

Loading diagram...

All Problems