# 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
$.& 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.

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


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


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 # 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

# 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