Shortest Unique Substring

Question

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

Answer 1

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
               }

Answer 2

Python, 119 115 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.

Answer 3

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.

Answer 4

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:''.

Answer 5

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

Answer 6

Pyth, 11 bytes

Jwhf!}TJ.:z

Try it online!

Answer 7

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.

Answer 8

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.

Answer 9

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');

Answer 10

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.

Answer 11

Burlesque - 26 bytes

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

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

Answer 12

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

Answer 13

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

Answer 14

Pyth - 9 6 bytes

h-Fm.:

Try it online here.

Answer 15

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;}

Answer 16

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}