# Shortest Unique Substring

Given (on STDIN, as command line arguments, or as function arguments) two distinct non-empty strings, find and return the shortest substring of the first string which is not a substring of the second. If no such substring exists, you may return the empty string, return any string which isn't a substring of the original string, or throw an exception. If you are returning from a function, you may also return null (or undefined, None, etc.) in this case. If multiple such substrings are tied for the shortest, you may return any one of them.

Strings can consist of any printable ascii characters.

Input given on STDIN will be given with one string on each line. At your request, a single empty line may be added at the end of the input.

This is code golf, so the shortest valid program wins.

# SOME TEST CASES

INPUT:

STRING ONE
STRING TWO

OUTPUT:

E

INPUT:

A&&C
A&$C VALID OUTPUTS: && &C INPUT: (Two randomly-generated 80-letter strings) QIJYXPYWIWESWBRFWUHEERVQFJROYIXNKPKVDDFFZBUNBRZVUEYKLURBJCZJYMINCZNQEYKRADRYSWMH HAXUDFLYFSLABUCXUWNHPSGQUXMQUIQYRWVIXGNKJGYUTWMLLPRIZDRLFXWKXOBOOEFESKNCUIFHNLFE ALL VALID OUTPUTS: AD BJ BR CZ DD EE ER EY EY FF FJ FW FZ HE IJ IN IW JC JR JY KL KP KR KV LU MH MI NB NQ OY PK PY QE QF QI RA RB RF RO RV RY RZ SW UE UH UN UR VD VQ VU WB WE WI WU XN XP YI YK YK YM YS YW YX ZB ZJ ZN ZV • shortest or longest? – Leaky Nun Apr 29 '16 at 15:12 • @FryAmTheEggman Then should I still post my solution... – Leaky Nun Apr 29 '16 at 15:15 • "One string on each line" with or without quotes? – Leaky Nun Apr 29 '16 at 15:21 • Can we take an array of strings? – Dennis Apr 29 '16 at 17:16 • is "B" a substring of "aBc" ? – downrep_nation Apr 29 '16 at 17:58 ## 16 Answers # Brachylog, 23 bytes :1foh.,{,.[A:B]hs?'~sB} Works on the old Java transpiler. Expects the two strings in a list as input, unifies the output with the substring. If no substring is found, returns false. Unfortunately I have not yet coded the subset built-in in the new Prolog transpiler. ### Explanation :1f Find all bindings which satisfy predicate 1 with that binding as input and with the Input of the main predicate as output. oh., Order that list of bindings, and unify the output with the first one. { ,.[A:B] Unify the output with the list [A,B] hs? Unify the input with a subset of A '~sB Check that no subset of B can be unified with the input } # Python, 119115 91 lambda a,b:[a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a))if a[m:m+n]not in b][0] Test cases: | Input 1 | Input 2 | Output | |----------+-------------+---------------| | 'abcd' | 'abc' | 'd' | | 'abcd' | 'dabc' | 'cd' | | 'abcd' | 'dcbabbccd' | 'abc' | | 'abcdf' | 'abcdebcdf' | 'abcdf' | | 'abc' | 'abc' | (IndexError) | Working on making it shorter, but this is my brain instinct. Not really much of a golfer yet. Thanks to @user81655 and @NonlinearFruit for the extra bytes. Edit: Dang. Tried this code: def z(a,b): for s in [a[m:m+n]for n in range(1,len(a)+1)for m in range(len(a)-n+1)]: if s not in b:return s return'' Thought it was a few bytes shorter. Turns out it was 1 byte longer than what I had before the edit. • I don't know much python, but maybe you can do (r=range)(1,len(a)+1) then use r? – Conor O'Brien Apr 29 '16 at 16:03 • @CᴏɴᴏʀO'Bʀɪᴇɴ Can't do it quite that way. If I assign range to r in the line above, it actually adds a byte. Good idea, though. There's probably a shorter way to iterate through the substrings. – Taylor Lopez Apr 29 '16 at 16:07 • range(1,len(a)) and range(len(a)-1) should work shouldn't it? Also I think using a tab character for the two space indent would save a byte. – user81655 Apr 29 '16 at 16:17 • No, with range(1,len(a)), the 4th test cast fails because it won't try the full string; it'll only go to the length of the string - 1. And with range(len(a)-1), the 1st test case fails returning 'cd' instead of just 'd'. There may be something there, though. – Taylor Lopez Apr 29 '16 at 16:22 • Sorry, I'm not familiar with Python and I assumed the ranges were inclusive. In that case try range(1,len(a)+1) and range(len(a)). – user81655 Apr 29 '16 at 16:34 # Python, 87 86 bytes lambda s,t,e=enumerate:[s[i:i-~j]for j,_ in e(s)for i,_ in e(s)if(s[i:i-~j]in t)<1][0] If it exists, this will return the leftmost of all shortest unique substrings. If there is no unique substring, an IndexError is raised. Test it on Ideone. • There it is. I was waiting for somebody to kill my non-lambda implementation. nice lol – Taylor Lopez Apr 29 '16 at 18:03 • I think you can make this shorter by supplying the optional second argument to enumerate to start j at i+1. – user2357112 Apr 29 '16 at 23:25 • @user2357112 That throws a NameError, unfortunately. The code defines j first, then i. – Dennis Apr 29 '16 at 23:39 • @Dennis: Yeah, but it doesn't need to. You could switch the loop order. – user2357112 Apr 29 '16 at 23:41 • @user2357112 If I switch the loop order, the first unique substring it finds may not be the shortest. Simply swapping the order returns 'ab' for input 'abc','aaa'. – Dennis Apr 29 '16 at 23:44 # Python, 82 bytes g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''} f=lambda s,t:min(g(s)-g(t),key=len) Usage: f('A&&C', 'A&$C') -> returns '&&'

Raises ValueError if there is no suitable substring.

Explanation:

g=lambda u:{u}|g(u[1:])|g(u[:-1])if u else{''} recursively creates a set of the substrings of u f=lambda s,t:min(g(s)-g(t),key=len) takes the shortest substring from the set difference

## JavaScript (ES6), 79 bytes

f=
(a,b)=>[...a].some((_,i,c)=>c.some((_,j)=>b.indexOf(s=a.substr(j,i+1))<0))?s:''
<div oninput=o.textContent=f(a.value,b.value)><input id="a"/><input id="b"/><pre id=o>

If returning false is acceptable, save 2 bytes by using &&s instead of ?s:''.

Jwhf!}TJ.:z

Try it online!

# JavaScript (Firefox), 80 bytes

solution=

a=>b=>[for(_ of(i=0,a))for(_ of(j=!++i,a))if(b.includes(s=a.substr(j++,i)))s][0]

document.write("<pre>"+
[ [ "test", "best" ], [ "wes", "west" ], [ "red", "dress" ] ]
.map(c=>c+": "+solution(c[0])(c[1])).join\n)

Test works only in Firefox. Returns undefined if there is no substring.

• Strings could contain printable ASCII characters such as \ or other RegExp metacharacters, but if you're limiting yourself to Firefox, why not use b.includes instead? – Neil Apr 29 '16 at 18:31
• @Neil The question didn't say that the strings could be any character before but thanks for letting me know! Updated to use includes. – user81655 Apr 29 '16 at 18:34
• The test snippet throws a SyntaxError: unexpected token 'for' – NoOneIsHere Apr 29 '16 at 19:35
• @NoOneIsHere That's the error you'll get if you're not using Firefox... – user81655 Apr 29 '16 at 20:30

## Retina, 37 bytes

M!&\G(.+?)(?!.*¶.*\1)
O$#.+$.&
G1

Output is empty if no valid substring is found in A.

Try it online! (Slightly modified to run several test cases at once. The input format is actually linefeed separated, but test suites are easiest to write with one test case per line. The test framework turns the space into a linefeed before the actual code starts.)

### Explanation

M!&\G(.+?)(?!.*¶.*\1)

For each possible starting position in A, match the shortest substring which does not appear in B. The & is for overlapping matches, such that we actually try every starting position, even if a match is longer than one character. The \G ensures that we don't skip any positions - in particular, this way we have to stop at the linefeed, such that we don't get additional matches from B itself. The reason this doesn't mess things up is actually quite subtle: because if there's a starting position in A where we can't find any valid substring, then that's also a failure which will cause \G to stop checking any further positions. However, if (from the current starting position) all substrings appear in B, so will all substrings that start further right of the current position, so discarding those is not an issue (and actually improves performance).

Due to the M! configuration, all of these matches will be returned from the stage, joined with linefeeds.

O$#.+$.&

This sorts the lines of the previous result by length. This is done by matching the line with .+. Then $activates a form of "sort-by", such that the match is substituted with$.& for determining sort order. The $.& itself replaces the match with its length. Finally, the # option tells Retina to sort numerically (otherwise, it would treat the resulting numbers as strings and sort them lexicographically). G1 Finally, we simply keep only first line, by using a grep stage with an empty regex (which always matches) and a limit of 1. # Perl, 87 85 sub{(grep{$_[1]!~/\Q$_/}map{$}=$_;map{substr($_[0],$_,$})}@}}(@}=0..length$_[0]))[0]} This is an anonymous function which returns the first (by position) of the shortest substrings of$_[0] that do not occur in $_[1], or undef if no such substring exists. Test program with strings taken from @iAmMortos's answer, tested with Perl 5.22.1: #!/usr/bin/perl -l use strict; use warnings; my$f = <see above>;
print $f->('abcd', 'abc'); print$f->('abcd', 'dabc');
print $f->('abcd', 'dcbabbccd'); print$f->('abcdf', 'abcdebcdf');
print $f->('abc', 'abc'); ## Haskell, 72 bytes import Data.Lists a#b=argmin length[x|x<-powerslice a,not$isInfixOf x b]

Usage example: "abcd" # "dabc"-> "cd".

A straightforward implementation: build all substrings of a and keep those which do not appear in b. argmin returns an element of a list which minimizes the function given a the 2nd argument, here: length.

• I didn't know about argmin! It seems extremely useful. – Zgarb Apr 30 '16 at 16:58

# Pyth - 9 6 bytes

h-Fm.:
• Crossed out 9 is still 9 – cat Apr 30 '16 at 15:33
• I'd love to know how this works. – mroman Nov 25 '18 at 14:02
• @mroman the .: with one arg is all substrs. So I map that over both strings, then fold setwise diff, so I have all substrs of first that arnt of the second, then I pick the first one, which is smallest cuz .: is sorted. – Maltysen Nov 25 '18 at 19:03

## C#, 152 bytes

string f(string a,string b){int x=a.Length;for(int i=1;i<=x;i++)for(int j=0;j<=x-i;j++){var y=a.Substring(j,i);if(!b.Contains(y))return y;}return null;}

# Ruby, 70 bytes

Collects all substrings of a certain length from the first string, and if there is one that isn't in the second string, return it.

->a,b{r=p;(1..l=a.size).map{|i|(0...l).map{|j|b[s=a[j,i]]?0:r||=s}};r}

## Burlesque - 26 bytes

Right now the shortest way I can come up with is:

lnp^sujbcjz[{^p~[n!}f[-][~

# Japt, 14 bytes

Êõ!ãU c k!èV g

Try it online!

Returns undefined if there is no valid substring. This is distinct from returning the string "undefined", though the difference is only visible because of the -Q flag.

Explanation:

Ê                 :Length of the first input
õ                :For each number in the range [1...length]:
!ãU             : Get the substrings of the first input with that length
c           :Flatten to a single array with shorter substrings first
k         :Remove ones which return non-zero to:
!èV      : Number of times that substring appears in second input
g    :Return the shortest remaining substring

# Japt -h, 11 bytes

à f@øX «VøX

Try it

:Implicit input of strings U & V
à               :All combinations of U
f@            :Filter each as X
øX          :  Does U contain X?
«        :  Logical AND with the negation of
VøX     :  Does V contain X?
:Implicit output of last element