Shortest Unique Substrings

Question

Input

An alphanumeric string s.

Output

The shortest string that occurs exactly once as a (contiguous) substring in s. Overlapping occurrences are counted as distinct. If there are several candidates of the same length, you must output all of them in the order of occurrence. In this challenge, the empty string occurs n + 1 times in a string of length n.

Example

Consider the string

"asdfasdfd"

The empty string occurs 10 times in it, so it is not a candidate for unique occurrence. Each of the letters "a", "s", "d", and "f" occurs at least twice, so they are not candidates either. The substrings "fa" and "fd" occur only once and in this order, while all other substrings of length 2 occur twice. Thus the correct output is

["fa","fd"]

Rules

Both functions and full programs are allowed, and standard loopholes are not. The exact formatting of the output is flexible, within reason. In particular, producing no output for the empty string is allowable, but throwing an error is not. The lowest byte count wins.

Test cases

"" -> [""]
"abcaa" -> ["b","c"]
"rererere" -> ["ererer"]
"asdfasdfd" -> ["fa","fd"]
"ffffhhhhfffffhhhhhfffhhh" -> ["hffff","fffff","hhhhh","hfffh"]
"asdfdfasddfdfaddsasadsasadsddsddfdsasdf" -> ["fas","fad","add","fds"]

Leaderboard

Here's the by-language leaderboard that I promised.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

<script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>site = 'meta.codegolf',postID = 5314,isAnswer = true,QUESTION_ID = 45056;jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)<\\/code><\/pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>

Answer 1

Python 3, 124 123 111 96 bytes

f=lambda s,n=1:[x for x in[s[i:i+n]for i in range(len(s)+1)]if s.find(x)==s.rfind(x)]or f(s,n+1)

Looks for strings such that the first occurrence from the left is the same as the first occurrence from the right. The +1 in the range is to accommodate for the empty string case.

Now if only Python had a .count() which counted overlapping matches, then this would have been a fair bit shorter.

Answer 2

Mathematica, 95 94 79 bytes

Cases[Tally@StringCases[#,___,Overlaps->All],{s_,1}:>s]~MinimalBy~StringLength&

StringCases gets me all possible substrings, the Tally and Cases filter out those that appear more than once and MinimalBy finds those that are shortest.

Answer 3

GolfScript, 44 bytes

:S;-1:x{;S,x):x-),{S>x<}%:^1/{^\/,2=},.!}do`

Takes input as a string on stdin and outputs in a double-array syntax: e.g. [["b"] ["c"]]. Online demo

Dissection

:S;          # Store input in S and pop it
-1:x         # Store -1 in x
{            # do-while loop
  ;          #   Pop x the first time and [] every subsequent time
  S,x):x-),  #   Increment x and build an array [0 1 ... len(S)-x]
  {S>x<}%    #   Map that array to [substr(S,0,x) substr(S,1,x) ...]
  :^         #   Store in ^ (to avoid the token coalescing with the next char)
  1/         #   Split by length 1 to iterate over 1-elt arrays rather than strings
  {^\/,2=},  #   Filter to arrays which occur exactly once as a subarray of ^
  .!         #   Duplicate and test emptiness
}do          # end do-while loop: loop if the filtered array is empty
`            # Stringify for output

This is arranged such that no special case is required for the empty string (which I've included as a test case in the online demo linked above).

Answer 4

Pyth, 27 26 bytes

&zhfTmf!/>zhxzYYm<>zkdUzUz

Try it here.

Note that due to a bug in the online compiler, the empty string case only works correctly on the command line version, which can be found here.

You can also cure the bug by giving a newline as the input for the online compiler.

Explanation:

                                   z = input(), implicit.
&z                                 Prints empty string if input is empty.
  hfT                              Take the first non-empty list from
     m                  Uz         A list of list of substrings of z, divided by length
                m<>zkdUz           with some shorter strings repeated later, to no effect.
      f                            Where the substrings are filtered on
       !/      Y                   There being 0 occurrences of the substring in
         >z                        The slice of z
           hxzY                    from the character after the first character
                                   of the first occurrence of the substring in z
                                   to the end of z.

Answer 5

CJam, 52 43 40 bytes

]]q:Q,,{)Q,1$-),f{Q><}:R{R\a/,2=},}%{}=p

Input is the string without quotes

Explanation:

]]                                       "For empty string input case";
  q:Q                                    "Read the input and store in Q";
     ,,                                  "Take length of input and 0 to length array";
       {                          }%     "Map the above array on this code block";
        )Q                               "Increment the number in the current iteration, L";
         Q,1$                            "Take input's length and copy the above number";
             -)                          "Get upper limit of next loop to get substrings";
               ,f{   }                   "Get 0 to above number array and for each";
                  Q><                    "Get the L length substring at Ith index where";
                                         "I loops from 0 to Q, - L + 1";
                      :R                 "Store this list of substring of length L in R";
                        {R\a/,2=},       "Filter to get unique substrings";
                                    {}=  "Get the first non empty substring array";
                                         "This leaves nothing on stack if all are empty";
                                       p "Print the top stack element. At this point, its";
                                         "Either the first non empty substring array or";
                                         "the ]] i.e. [""] which we added initially";

                       

Example:

asdfdfasddfdfaddsasadsasadsddsddfdsasdf

Output

["fas" "fad" "add" "fds"]

Try it online here

Answer 6

Scala, 120 bytes

readLine.inits.flatMap(_.tails).toList.groupBy(l=>l).filter(x=>x._2.length<2).map(_._1).groupBy(_.length).minBy(_._1)._2

I started off with 140 which at least already fits into a tweet.

(                                        // added for comments
 readLine                                // input
.inits.flatMap(_.tails).toList           // get all substrings of that string
.groupBy(l=>l).filter(x=>x._2.length<2)  // remove substrings that occur more than once
.map(_._1).groupBy(_.length)             // take the substring and group by length
.minBy(_._1)._2                          // take the list of shortest substrings
)

Answer 7

JavaScript (ES6), 109 110

Edit search instead of indexOf, as the input string is alphanumeric. Thanks @IsmaelMiguel

Recursive function, looking for substrings starting with length 1 and going up.

F=(s,n=1,r)=>
s?[...s].map((a,i)=>~s.indexOf(a=s.substr(i,n),s.search(a)+1)?r:r=[...r||[],a])&&r||F(s,n+1):[s]

Ungolfed and explained

 F = function(s, n=1) { // start with length 1
   var i, a, p, r;
   if (s == "") // special case for empty input string
     return [s];
   for (i = 0; i < s.length; i++) 
   // for each possibile substring of length n
   // (should stop at s.length-n+1 but going beyond is harmless)
   // Golfed: "[...s].map((a,i)" ... using i, a is overwrittem
   {
     a = s.substr(i, n); // substring at position i
     p = s.search(a); // p is the first position of substring found, can be i or less
     p = s.indexOf(a, p + 1) // p is now the position of a second instance of substring, or -1 if not found
     if (~p) // ~p is 0 if p is -1
     {
       ; // found more than once, do nothing
     }
     else
     {
       r = r || []; // if r is undefined, then it becomes an empty array
       r.push(a); // save substring 
       // Golfed: "r=[...r||[],a]"
     }
   }
   if (r) // if found some substring, saved in r
   {
     return r;
   }
   return F(s, n+1) // recursive retry for a bigger length
 }

Test In FireFox/FireBug console

;["", "abcaa", "rererere", "asdfasdfd", "ffffhhhhfffffhhhhhfffhhh", 
 "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"]
.forEach(x=>console.log(x,F(x)))

Output

 [""]
abcaa ["b", "c"]
rererere ["ererer"]
asdfasdfd ["fa", "fd"]
ffffhhhhfffffhhhhhfffhhh ["hffff", "fffff", "hhhhh", "hfffh"]
asdfdfasddfdfaddsasadsasadsddsddfdsasdf ["fas", "fad", "add", "fds"]

Answer 8

Java, 168 176 233

Here's a pretty basic nested loop example.

void n(String s){for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)for(String b;i<=t-l;)if(s.indexOf(b=s.substring(i,i+++l),s.indexOf(b)+1)<0){System.out.println(b);q++;}}

Or a bit more readable:

void t(String s){
    for(int l=0,i=0,t=s.length(),q=0;l++<t&q<1;i=0)
        for(String b;i<=t-l;)
            if(s.indexOf(b=s.substring(i,i++ +l),s.indexOf(b)+1)<0){
                System.out.println(b);
                q++;
            }
}

Answer 9

Haskell, 169 162 155 153 151 138 120 115

import Data.List
l=length
q k=filter$(==)k.l
p y=q(minimum.map l$y)$y
f x=p$concat$q 1$group$sort$(tails x>>=inits)

To use it:

f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"

Which gives:

["add","fad","fas","fds"]

Btw. I hate the last line of my code (repetition of h y). Anyone hints to get rid of it?

Answer 10

J, 61 58 44 42 40 38 37 bytes

[:>@{.@(#~#@>)#\<@(~.#~1=#/.~)@(]\)]

Here is a version split up into the individual components of the solution:

unqs =. ~. #~ 1 = #/.~               NB. uniques; items that appear exactly once
allsbsq =. #\ <@unqs@(]\) ]        NB. all unique subsequences
shrtsbsq =. [: >@{.@(#~ #@>) allsbsq NB. shortest unique subsequence

• x #/. y computes for each distinct element in x how often in occurs in y. If we use this as y #/. y, we get the for each distinct element in y its count. For instance, a #/. a for a =. 1 2 2 3 4 4 yields 1 2 1 2.
• 1 = y checks which items of y are equal to 1. For instance, 1 = a #/. a yields 1 0 1 0.
• u~ is the reflexive of a monadic verb u. This is, u~ y is the same as y u y. Thus, #/.~ y is the same as #/.~ y. When applied to a dyadic verb, u~ is the passive of u. That is, x u~ y is the same as y u x. These are used in quite a few other places which I do not explicitly mention.
• ~. y is the nub of y, a vector with duplicates removed. For instance, ~. a yields 1 2 3 4.
• x # y (copy) selects from y the items at the indices where x contains a 1.
• Thus, (1 = y #/. y) # (~. y) creates a vector of those elements of y which appear only once. In tacit notation, this verb is written as ~. #~ 1 = #/.~; let's call this phrase unqs for the rest of the explanation.

• x ]\ y creates an x by 1 + y - x array of all infixes of the vector y of length x. For instance, 3 ]\ 'asdfasdfd yields

  asd
  sdf
  dfa
  fas
  asd
  sdf
  dfd
  

• # y is the tally of y, that is, the number of elements in y.

• u\ y applies u to each prefix of y. Incidentally, #\ y creates a vector of integers from 1 to #y.
• < y puts y into a box. This is needed because arrays cannot be ragged and we compute an array of suffixes of different lengths; a boxed array counts as a scalar.

• Thus, (i. # y) <@:unqs@(]\) y generates a vector of #y boxed arrays of the length k (for all 0 ≤ k < #y) infixes of y that occur exactly once. The tacit form of this verb is i.@# <@unqs@(]\) ] or i.@# <@(~. #~ 1 = #/.~)@(]\) ] if we don't use the unqs name. Let's call this phrase allsbsq for the rest of this explanation. For instance, allsbsq 'asdfasdfd' yields:

  ┌┬─┬──┬───┬────┬─────┬──────┬───────┬────────┐
  ││ │fa│dfa│sdfa│asdfa│asdfas│asdfasd│asdfasdf│
  ││ │fd│fas│dfas│sdfas│sdfasd│sdfasdf│sdfasdfd│
  ││ │  │dfd│fasd│dfasd│dfasdf│dfasdfd│        │
  ││ │  │   │sdfd│fasdf│fasdfd│       │        │
  ││ │  │   │    │asdfd│      │       │        │
  └┴─┴──┴───┴────┴─────┴──────┴───────┴────────┘
  

• (#@> y) # y takes from vector of boxed arrays y those which aren't empty.

• {. y takes the first element of vector y.
• > y removes the box from y.
• Thus, > {. (#@> y) # y yields the unboxed first non-empty array from vector of boxed arrays y. This phrase is written >@{.@(#~ #@>) in tacit notation.

• Finally, [: >@{.@(#~ #@>) allsbsq assembles the previous phrase with allsbsq to create a solution to the problem we have. Here is the full phrase with spaces:

  [: >@{.@(#~ #@>) i.@# <@(~. #~ 1 = #/.~)@(]\) ]
  

Answer 11

Haskell, 135 Bytes

import Data.List
f ""=[""]
f g=map(snd)$head$groupBy(\a b->fst a==fst b)$sort[(length y,y)|[y]<-group$sort[x|x@(_:_)<-tails g>>=inits]]

Answer 12

PHP, 171 152 134 125

function f($s){while(!$a&&++$i<strlen($s))for($j=0;$b=substr($s,$j++,$i);)strpos($s,$b)==strrpos($s,$b)&&($a[]=$b);return$a;}

http://3v4l.org/RaWTN

Answer 13

Groovy (Java regex on Oracle implementation), 124

c={m=it=~/(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))/;o=m.collect({it[1]});o.findAll({it.size()==o.min({it.size()}).size()});}

Tested on Groovy 2.4 + Oracle JRE 1.7. The regex should work for Java 6 to Java 8, since the bug that allows the code above to work is not fixed. Not sure for previous version, since there is a look-behind bug in Java 5 which was fixed in Java 6.

The regex finds the shortest string which doesn't have a duplicate substring elsewhere, at every position in the input string. The code outside takes care of filtering.

(?=(.*?)(?=(.*))(?<=^(?!.*\1(?!\2$)).*))

• Since the strings can overlap, I surround the whole thing in look-ahead (?=...).
• (.*?) searches from the shortest substring
• (?=(.*)) captures the rest of the string to mark the current position.
• (?<=^(?!.*\1(?!\2$)).*) is an emulation of variable-length look-behind, which takes advantage of the implementation bug which allows (?<=.*) to pass the length check.

• (?!.*\1(?!\2$)) simply checks that you can't find the same substring elsewhere. The (?!\2$) rejects the original position where the substring is matched.

  The limit of the outer look-around construct doesn't apply to the nested look-around construct. Therefore, the nested negative look-ahead (?!.*\1(?!\2$)) actually checks for the whole string, not just up to the right boundary of the look-behind.

Answer 14

Rebol, 136 bytes

f: func[s][repeat n length? b: copy s[unless empty? x: collect[forall s[unless find next find b t: copy/part s n t[keep t]]][return x]]]

Ungolfed:

f: func [s] [
    repeat n length? b: copy s [
        unless empty? x: collect [
            forall s [
                unless find next find b t: copy/part s n t [keep t]
            ]
        ][return x]
    ]
]

Usage example:

>> f ""       
== none

>> f "abcaa"
== ["b" "c"]

>> f "rererere"
== ["ererer"]

>> f "asdfasdfd"
== ["fa" "fd"]

>> f "ffffhhhhfffffhhhhhfffhhh"
== ["hffff" "fffff" "hhhhh" "hfffh"]

>> f "asdfdfasddfdfaddsasadsasadsddsddfdsasdf"
== ["fas" "fad" "add" "fds"]

NB. I suppose the heart of the code is how the find part is working. Hopefully this will help explain...

>> find "asdfasdfd" "df"
== "dfasdfd"

>> next find "asdfasdfd" "df"
== "fasdfd"

>> find next find "asdfasdfd" "df" "df"
== "dfd"

>> ;; so above shows that "df" is present more than once - so not unique
>> ;; whereas below returns NONE because "fa" found only once - ie. bingo!

>> find next find "asdfasdfd" "fa" "fa"
== none

Answer 15

Haskell, 119

f s=[r|n<-[1..length s],l<-[map(take n)$take(length s-n+1)$iterate(drop 1)s],r<-[[j|j<-l,[j]==[r|r<-l,r==j]]],r/=[]]!!0

Answer 16

Brachylog, 10 bytes

sᶠ≡ᵍ~gˢlᵍt

Try it online!

sᶠ            The list of every substring of the input
  ≡ᵍ          grouped by identity,
    ~gˢ       with length-1 groups converted to their elements and other groups discarded,
       lᵍ     and grouped by their length,
         t    has the output as its last group.

Although ᵍ doesn't naturally sort by the value it groups by, instead ordering the groups by the first occurrence of each value, the first occurrences of every length are in decreasing order. I'm not 100% sure that the uniqueness filtering can't mess this up, but I haven't come up with a test case this fails yet.

Answer 17

05AB1E, 10 bytes

Œʒ¢}é.γg}н

Outputs nothing for an empty string.

Try it online or verify all test cases.

Explanation:

Π          # Get all substrings of the (implicit) input-String
 ʒ          # Filter it by:
  ¢         #  Count how many times the current substring occurs in the (implicit) input-String
            #  (only 1 is truthy in 05AB1E, so the filter will leave unique substrings)
   }é       # After the filter: sort the remaining substrings by length
     .γg}   # Then group them by length as well
         н  # And only leave the first group containing the shortest substrings
            # (which is output implicitly as result)

This takes advantage of 05AB1E's only having 1 as truthy value, and everything else as falsey. The shortest unique substring is always guaranteed to occur exactly once for all possible input-strings. (For an input-string containing only the same characters (i.e. aaaaa), the input-strings itself as substring occurs just once, so the result is ["aaaaa"]. For an input-String with repeating pattern (i.e. "abcabc"), there are still unique substrings that only occur once (["abca","abcab","abcabc","bca","bcab","bcabc","ca","cab","cabc"]), so this will result in ["ca"].)

Answer 18

Python 2, 150

import re
a=input()
r=range
l=len(a)
d=0
for i in r(l):
 if d:break
 for j in r(l-i):
  k=a[j:i+j+1]
  if len(re.findall("(?="+k+")",a))<2:d=1;print k

Answer 19

Perl 5 -a, 114 87 bytes

map{//;(grep$' eq$_,@q)-1||($l||=y///c)-y///c||say}@q=map{"@F"=~/(?=(.{$_}))/g}1..y///c

Try it online!

Old method: 114 bytes