Subsequence Validator

EASY10 pts

You are given two strings: a pattern string s and a source string t. Your task is to determine whether the pattern can be derived from the source by removing zero or more characters while maintaining the original relative order of the remaining characters.

A derived subsequence is formed by selecting characters from a string in left-to-right order (not necessarily contiguous) without rearranging them. For instance, "ace" can be derived from "abcde" by selecting the characters at positions 0, 2, and 4, but "aec" cannot be derived from "abcde" because it would require rearranging the relative positions of 'e' and 'c'.

Return true if s is a valid derived subsequence of t, otherwise return false.

Example

Input

s = "abc"
t = "ahbgdc"

Output

true

Explanation

The characters 'a', 'b', and 'c' appear in "ahbgdc" in the same relative order. We can derive "abc" by selecting positions 0, 2, and 5 from the source string.

Example

Input

s = "axc"
t = "ahbgdc"

Output

false

Explanation

While 'a' and 'c' exist in "ahbgdc", the character 'x' does not appear in the source string at all. Therefore, "axc" cannot be derived as a subsequence.

Example

Input

s = "ace"
t = "abcde"

Output

true

Explanation

The pattern "ace" can be derived from "abcde" by selecting the characters at indices 0, 2, and 4. The relative ordering is preserved as 'a' comes before 'c', which comes before 'e'.

Accepted0/0·0% Acceptance

Constraints

0 ≤ s.length ≤ 100
0 ≤ t.length ≤ 10⁴
Both `s` and `t` contain only lowercase English letters (a-z).

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

s =

"abc"

t =

"ahbgdc"

Return true if s is a valid derived subsequence of t, otherwise return false.

Subsequence Validator

Hints

Subsequence Validator

Hints