# Is string X a subsequence of string Y?

Given strings X and Y, determine whether X is a subsequence of Y. The empty string is regarded as a subsequence of every string. (E.g., '' and 'anna' are subsequences of 'banana'.)

### Input

• X, a possibly-empty case-sensitive alphanumeric string
• Y, a possibly-empty case-sensitive alphanumeric string

### Output

• True or False (or equivalents), correctly indicating whether X is a subsequence of Y.

### I/O examples

X      Y        output

''     'z00'    True
'z00'  'z00'    True
'z00'  '00z0'   False
'aa'   'anna'   True
'anna' 'banana' True
'Anna' 'banana' False


### Criteria

• The shortest program wins, as determined by the number of bytes of source code.

### Example programs

• Why is 'anna' substr of 'banana'?
– kaoD
Apr 26, 2012 at 5:04
• @kaoD - anna is a subsequence (but not a substring) of banana. String X is a subsequence of string Y just if X can be obtained from Y by deleting zero or more of the elements of Y; e.g., deleting the b and the second a from banana gives anna. Apr 26, 2012 at 13:33
• This has about a single solution in every scripting language offering regex that's both trivial to see and impossible to golf further.
– Joey
Apr 27, 2012 at 14:50

# PHP, 7565 64 bytes

for(;$p=@strpos(_.$argv[2],$c=$argv[1][$i++],$p+1););echo""==$c;  takes input from command line arguments; prints 1 for true, empty string for false. Run with -r. explanation: • strpos returns false if needle $c is not in the haystack $argv[2] (after position $p),
causing the loop to break.
• strpos also returns false for an empty needle, breaking the loop at the end of $argv[1]. • If $argv[1] is a subsequence of $argv[2], $c will be empty when the loop breaks.
• strpos needs @ to suppress Empty needle warning.
• +$p instead of $p+1 after that ther is no need for the underscore Mar 14, 2017 at 17:47
• @JörgHülsermann +1 is needed to advance in the haystack string; and the underscore avoids $p=-1 initialization. But ... I can avoid false!==. Mar 14, 2017 at 17:50 # Swift, 27 print(Y.range(of:X) != nil)  • Welcome to PPCG! May 19, 2017 at 21:13 # APL (Dyalog Unicode), 18 bytesSBCS Full program. Prompts for Y then for X. ×≢(∊'.*'∘,¨⍞)⎕S⍬⊢⍞  Try it online! ⍞ prompt (for Y) ⊢ yield that (separates ⍬ from it) ()⎕S⍬ search for occurrences of the following, yielding one empty list for each match: ⍞ prompt (for X) '.*'∘,¨ prepend .* to each character ∊ϵnlist (flatten) ≢ tally the number of matches × sign of that # APL(NARS), chars 46, bytes 92 {(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵}  test:  h←{(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵} '' h 'z00' 1 'z00' h 'z00' 1 'z00' h '00z0' 0 'aa' h 'anna' 1 'anna' h 'banana' 1 'Anna' h 'banana' 0  comment: {(⊂,⍺)∊(⊂''),↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵} ⍳¯1+2*k←≢w←⍵ this assign to w the argument and k argument lenght, it return 1..(2^k)-1 range {⍵⊤⍨k⍴2}¨ for each element of 1..(2^k)-1 convert in base 2 with lenght k (as the arg lenght) {⍵⊂w}¨ use the binary array above calculation for all partition argument ,/¨ concatenate each element of partition ↑¨ get the firs element of each element because they are all enclosed (⊂''), add to the array the element (⊂'') (⊂,⍺)∊ see if (⊂,⍺) is one element of the array, and return 1 true o 0 false  How all you can see the comments are +- superfluous all is easy... I have to say not understand why the last instruction is not "(,⍺)∊" in the place of "(⊂,⍺)∊" because for example in code  q←{↑¨,/¨{⍵⊂w}¨{⍵⊤⍨k⍴2}¨⍳¯1+2*k←≢w←⍵} o q '123' ┌7──────────────────────────────────────┐ │┌1─┐ ┌1─┐ ┌2──┐ ┌1─┐ ┌2──┐ ┌2──┐ ┌3───┐│ ││ 3│ │ 2│ │ 23│ │ 1│ │ 13│ │ 12│ │ 123││ │└──┘ └──┘ └───┘ └──┘ └───┘ └───┘ └────┘2 └∊──────────────────────────────────────┘ o (,'3') ┌1─┐ │ 3│ └──┘  all you see array of 1 element (,'3') is the element of the set of instruction q '123', but  o (,'3')∊q '123' ┌1─┐ │ 0│ └~─┘  return one array of unclosed 0 instead of number 1... for workaround that one has to write:  o (⊂,'3')∊q '123' 1 ~  that is the right result even if the element seems different because :  o (⊂,'3') ┌────┐ │┌1─┐│ ││ 3││ │└──┘2 └∊───┘  It is sure i make some error because i am not so smart... where is my error? # Perl 6, 34 28 bytes -6 bytes thanks to nwellnhof {$!=S:g/<(/.*/;&{?/<{$!}>/}}  Try it online! Anonymous code block that takes input curried, like f(X)(Y). This does the familiar join by .* and evaluate as a regex as other answers, but takes a couple of shortcuts. ### Explanation: { } # Anonymous code block$!=            # Assign to $! S:g/<(/.*/ # Inserting .* between every character ;&{ } # And return an anonymous code block ?/ / # That returns if the input matches <{$!}>     # The $! regex  # Jelly, 3 bytes ŒPi  Try it online! Outputs 0 for false and a non-negative integer for true ## How it works ŒPi - Main link. Takes X on the left and Y on the right ŒP - Powerset of X i - Index of y, or 0  # Java 8, 16316238 35 bytes a->b->b.matches(a.replace("",".*"))  -124 bytes by converting to Java 8, and pasting my answer from the duplicated challenge. NOTE: Doesn't work if the input contains special regex-characters, but this would invalidate a lot of existing answers as well. Try it online. Explanation: a->b-> // Method with two String parameters and boolean return-type b.matches( // Check if the second input matches the regex: a // The first input, .replace("",".*")) // where every character is surrounded with ".*"  For example: a="anna" b="banana"  Will do the check: "banana".matches("^.*a.*n.*n.*a.*$")

• You're mishandling special regexp characters like "." though Jan 26, 2021 at 18:02
• @StefanReich You're right, but the same applies to almost any other existing answer, though. But I've added a note to mention this in the answer (and golfed it by 3 bytes at the same time). Jan 26, 2021 at 19:44
• Come on... you're saying there is a bug in THIS? >> à øV << (the Japt program, whatever that is) Jan 26, 2021 at 21:53
• @StefanReich The golfing languages like Jelly, Japt, 05AB1E, etc. are probably fine, since most of them just use the powerset and check if the second input is in it. I was referring to the answers using regex like mine, like the accepted Perl answer; the Python answer of Eric; the Ruby answer; etc. All answers that use regex are similar as mine (add a ".*" after each characters, and check if it matches the second input) are most likely invalid if the inputs contain special regex characters. Jan 26, 2021 at 22:07
• I was just messing around :) Jan 26, 2021 at 22:43

# x86-16 machine code, 12 10 bytes

Binary:

00000000: 41ac f2ae e303 4a75 f8c3                 A.....Ju..


Unassembled listing:

41          INC  CX                 ; Loop counter is 1 greater than string length
SCAN_LOOP:
AC          LODSB                   ; load next char of acronym into AL
F2 AE       REPNZ SCASB             ; search until char AL is found
E3 03       JCXZ DONE               ; stop if end of first string reached
4A          DEC  DX                 ; decrement second string counter
75 F8       JNZ  SCAN_LOOP          ; stop if end of second string reached
DONE:


Callable function. Input: Y string pointer in SI, length in CX. X string pointer in DI, length in DX. Output is ZF if Truthy.

Example test program:

This test program uses additional PC DOS API I/O routines to take multi-line input from STDIN.

• x86-16 assembly is amazing! I thought this is going to take at least 20 bytes.
– user99151
Jan 28, 2021 at 6:49
• @2x-1 Yes it is! It's my goal to someday submit a valid answer to a question using only single-byte x86 instructions! Jan 29, 2021 at 17:45

# MMIX, 40 bytes (10 instrs)

C strings.

00000000: 8302 0000 8303 0100 dc04 0203 30FF 0203  ............0...
00000010: 73FF FF01 2200 00FF 2301 0101 5b04 fff9  s..."...#...[...
00000020: 7300 0201 f801 0000                      s.......


# Disassembly

subseq  LDBU $2,$0,0        // loop: av = *a
LDBU $3,$1,0        // bv = *v
MOR  $4,$2,$3 // t0 = av && bv (MOR is faster than MUL) CMP$255,$2,$3     // t1 = av <=> bv
ZSZ  $255,$255,1    // t1 = !t1
ADDU $0,$0,$255 // a += t1 ADDU$1,$1,1 // b += 1 PBNZ$4,subseq      // iflikely(t0) goto loop
ZSZ  $0,$2,1        // a = !t0
POP  1,0            // return a


Obvious algorithm, with only one branch!

For wchar_t, replace LDBU with LDWU (and similarly for codepoint_t); additionally, replace ADDU $0,$0,$255 with 2ADDU$0,$255,$0 (4ADDU for codepoints), and ADDU $1,$1,1 with ADDU $1,$1,2 or ADDU $1,$1,4.

## C, 120

main(i,c){char x[99],y[99];c=0;gets(y),gets(x);for(i=0;y[i]!='\0';)c+=y[i++]==x[c]?1:0;puts(x[c]=='\0'?"True":"False");}

• You can save at least 15 chars by moving c=0 to the loop initialiser and eliminating every instance of == in favour of "non-zero is truthy" conditions. Apr 16, 2012 at 16:36

## Javascript, 104 chars

function _(x,y){f=true;for(c in x){if(y.indexOf(x[c])>-1)y=y.replace(x[c],"");else{f=!f;break}}return f}


Ungolfed

function _(x,y){
f=true;
for(c in x)
{
if(y.indexOf(x[c])>-1)
y=y.replace(x[c],"");
else {
f=!f;
break;
}
}
return f;
}

• This appears to test whether x is a substring of y, but it's supposed to test whether x is a subsequence of y. E.g., 'anna' is a subsequence of 'banana', but 'banana'.indexOf('anna')>-1 evaluates to false. Sep 19, 2012 at 4:14
• @r.e.s. : My bad dint read the question properly. Thanks Sep 19, 2012 at 8:57
• @r.e.s. posted a altogether new answer Sep 19, 2012 at 9:17
• What does the new answer do for _("ab", "ba")? Sep 19, 2012 at 13:19
• returns true. demo jsfiddle.net/yvAdT Sep 19, 2012 at 18:28

# J (20 chars)

(<x)e.(#:i.2^#y)<@#y


The input is given in the variables x and y. It makes a list of all subsequences of y, so don't use it for very big strings.

# Python (72)

import itertools as I;any(tuple(X)==Z for Z in I.permutations(Y,len(X)))

• No, that use of permutations ignores the required order of the elements; e.g., X='z00' and Y='00z0' should output False (whereas your program outputs True). Mar 17, 2014 at 22:42

# Retina, 26 bytes (not competing)

The language is newer than the challenge. Byte count assumes ISO 8859-1 encoding. Input is taken on two lines with Y first.

+^(.)(.*¶)(?(\1).|)
$2 ¶$


Try it online

## JavaScript (ES6), 42 bytes

Takes input n (needle) and h (haystack) in currying syntax (n)(h).

n=>h=>!!RegExp(n.split.join.*).exec(h)


### Test

let f =

n=>h=>!!RegExp(n.split.join.*).exec(h)

console.log(f(''    )('z00'   )); // true
console.log(f('z00' )('z00'   )); // true
console.log(f('z00' )('00z0'  )); // false
console.log(f('aa'  )('anna'  )); // true
console.log(f('anna')('banana')); // true
console.log(f('Anna')('banana')); // false

• What if n contains regex special characters? Mar 14, 2017 at 16:11
• @Titus Well, I assumed n is in [A-Za-z0-9] since the challenge mentions that both input strings are alphanumeric. Mar 14, 2017 at 16:16
• woops missed that. :) Mar 14, 2017 at 16:36

# Pyth, 5 bytes (non-competing)

}hQye


Explanation

}hQye
hQ       The first input...
}         ... is an element of...
y      ... the power set...
eQ    ... of the second input.


## REXX, 76 bytes

o=1
do while x>''
parse var x a+1 x
parse var y(a)b+1 y
o=o&a=b
end
return o


Note that x and y are consumed by this routine. Readability is impaired by skipping a lot of whitespace and parentheses.

# Python 2, 47 bytes

x,y=map(list,input())
while x:y.remove(x.pop())


Try it online!

Takes two quote-delimited strings via STDIN as input.

Output is by presence or absence of an error, which is allowed per meta consensus.

Explanation:

             # get arguments from STDIN
input()
# convert each argument to a list
map(list,.......)
# split arguments into two variables
x,y=..................

# while x still has elements
while x:
# remove the final element of x and return its value
x.pop()
# remove the first matching item in y
# this will error if there is no matching element
y.remove(.......)

# if the loop is exited without error, all elements in x were in y

• This doesn't look like it checks that the removed letters are in the right order.
– xnor
Feb 22, 2019 at 17:16

# Japt, 4 bytes

Repost from a duplicate challenge.

Takes input in reverse order (Y, then X).

à øV


Try it

# Red, 82 bytes

func[x y][parse/case y collect[foreach c x[keep reduce['to c 'skip]]keep[to end]]]


Try it online!

# Julia 1.0, 53 bytes

f(x,y)=(x==""||[x=x[2:end] for c=y if c==x[1]];x=="")


Try it online!

# JavaScript, 32 bytes

Repost of a port of Kevin's Java solution to a duplicate challenge, modified in case my choices for I/O weren't standards at the time this challenge was posted.

x=>y=>!!y.match([...x].join.*)


Try it online! (will update with this challenge's test cases when I get back to a computer)

# Charcoal, 18 bytes

Ｆη≔✂θ⁼ι∧θ§θ⁰Ｌθ¹θ¬θ


Try it online! Link is to verbose version of code. Uses Charcoal's default Boolean output of - for true, nothing for false. Explanation:

Ｆη


Loop over the characters of Y.

⁼ι∧θ§θ⁰


See if this character is the next character of X.

≔✂θ...Ｌθ¹θ


If so then remove that character from X.

¬θ


Were all the characters of X consumed?

# 05AB1E, 3 bytes

æQà


Or alternatively:

æså


With both programs the first input is $$\Y\$$ and the second input is $$\X\$$.

Explanation:

æ    # Get the powerset of the (implicit) input-string Y
Q   # Check for each if it's equal to the (implicit) input-String X
à  # And check if any are truthy by taking the maximum
# (after which this result is output implicitly)

æ    # Get the powerset of the (implicit) input-String Y
s   # Swap to take the (implicit) input-String X
# (could also be I or ² to simply take input)
å  # Check if this string is in the powerset-list of strings
# (after which this result is output implicitly)


# Pyth, 5 bytes

}hQye


Try it online!

Pyth   | Explanation
-------+------------------------------------------
}hQye  | Full code
}hQyeQ | "       " with implicit variables
-------+------------------------------------------
}      | return whether arg0 is an element of arg1
hQ    |  first element of input
y   |  powerset of
eQ |   last element of input


# Husk, 2 bytes

€Ṗ


Try it online!

Having a single byte builtin for powerset is useful.

# Zsh-o glob_subst, 14 bytes

>:$1>${2///*}*


Try it online!

Explanation:

• >:$1: copy stdin to a file named : and the first argument. The colon ensures that we don't try to create a file with an empty name in the case of an empty string as input. Since we don't take any input from stdin, this just creates an empty file. • >${2///*}*: try to copy stdin (again) to a file that matches the pattern resulting from the expansion of ${2///*}* If no such file exists, an error will occur. The -o glob_subst ensures that the expanded value is treated as a pattern. Otherwise, it will be treated as a literal string. Alternatively, this option can be removed and ${~2///*}* used instead for +1 byte.
• ${2}: take the second argument • ///*: replace every empty string with an asterisk; this results in abc -> *a*b*c • append another asterisk. Asterisks simply mean "match any sequence # Lua, 8568 66 bytes _,b=...for c in (...):gmatch"."do b=b:gsub(c,"",1)end print(b=="")  Try it online! ### Explanation ... is the variable argument operator, it returns all remaining arguments to the current function (the top-level block in this case). We can force it to return just one variable by encasing it in parentheses. gmatch() is a pattern-matching function which returns an iterator function, we use it to loop over every character in the input string. gsub() is a substitution function, we use it to clear matched characters from the subset contender. The extra parameter is the number of substitutions to make, 1 in this case. # Vyxal, 6 bytes ṗƛṅ;$c
`

Try it Online!