29
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ Any limitations on combinatorial built-in functions? \$\endgroup\$ – Martin Ender Jan 27 '15 at 15:30
  • 3
    \$\begingroup\$ @MartinBüttner In this challenge, everything goes. If this gets enough answers, I'll put up a by-language leaderboard, so even the more ill-equipped languages can have a meaningful competition. \$\endgroup\$ – Zgarb Jan 27 '15 at 16:12
  • \$\begingroup\$ Do you want to use my code golf leaderboard snippet? Then you wouldn't have to monitor all edits to keep the leaderboard up-to-date. If you do, I can add it for you, and I'd go through the answers to make them match the header format. \$\endgroup\$ – Martin Ender Jan 28 '15 at 14:51
  • \$\begingroup\$ @MartinBüttner Thanks, I'd appreciate that! \$\endgroup\$ – Zgarb Jan 28 '15 at 14:55
  • \$\begingroup\$ All done! Let me know if something doesn't work. (Feel free to reuse it for your challenges in the future.) \$\endgroup\$ – Martin Ender Jan 28 '15 at 15:03

19 Answers 19

3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Fails for empty string input. \$\endgroup\$ – Optimizer Jan 27 '15 at 19:33
  • \$\begingroup\$ @Optimizer I think that's a bug in the online compiler, actually. It works on the command line version. In fact, z on no input fails online, so it's definitely a bug in the interpreter. \$\endgroup\$ – isaacg Jan 27 '15 at 19:45
  • \$\begingroup\$ Doesn't give EOF ? \$\endgroup\$ – Optimizer Jan 27 '15 at 19:46
  • \$\begingroup\$ @Optimizer Pyth expects newline terminated input, which might be what is going wrong. \$\endgroup\$ – isaacg Jan 27 '15 at 19:48
  • \$\begingroup\$ So passing an empty string is not even possible ? \$\endgroup\$ – Optimizer Jan 27 '15 at 19:49
13
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Isn't there an extra & at the end of the code? \$\endgroup\$ – David G. Stork Jan 28 '15 at 23:47
  • \$\begingroup\$ Boy, you're fast! \$\endgroup\$ – David G. Stork Jan 28 '15 at 23:48
4
\$\begingroup\$

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).

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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
)
\$\endgroup\$
  • \$\begingroup\$ I wonder? Why doesn't just (_) work as the identity instead of l=>l? \$\endgroup\$ – proud haskeller Jan 27 '15 at 18:59
  • \$\begingroup\$ I wonder too. Somehow list.groupBy(_) is the same as x => list.groupBy(x). I have no idea why they implemented it like that. \$\endgroup\$ – Dominik Müller Jan 27 '15 at 20:29
3
\$\begingroup\$

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"]
\$\endgroup\$
  • \$\begingroup\$ Use .search instead of .indexOf and you save 2 bytes. \$\endgroup\$ – Ismael Miguel Jan 28 '15 at 12:00
  • \$\begingroup\$ @IsmaelMiguel no because 1) search has not a offset parameter 2) search expect a regexp, and will fail with special chars like .*[] and so on \$\endgroup\$ – edc65 Jan 28 '15 at 12:04
  • 1
    \$\begingroup\$ But on the first you can safely replace it (on your s.indexOf(a)+1). While it's tue it won't work with those chars, you dont have to worry! Quoting the O.P: "Input: An alphanumeric string s." \$\endgroup\$ – Ismael Miguel Jan 28 '15 at 12:23
  • \$\begingroup\$ @IsmaelMiguel right, thanks. Missed the 'alphanumeric' constrain \$\endgroup\$ – edc65 Jan 28 '15 at 14:34
  • 1
    \$\begingroup\$ @IsmaelMiguel I did not find a way ... I need truthy or falsy, and any array (even empty []) is a truthy value in javascript \$\endgroup\$ – edc65 Jan 28 '15 at 15:31
3
\$\begingroup\$

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++;
            }
}
\$\endgroup\$
  • \$\begingroup\$ If you want readability, splitting +++ up to show whether it's + ++ or ++ + would help... And if you want to save a few more bytes, there might be a way to do that by initialising q=1, replacing q++ with q=t, and replacing l++<t&q<1 with something like t>l+=q. Probably requires tweaking one or two other offsets to get it to work. \$\endgroup\$ – Peter Taylor Jan 27 '15 at 18:05
  • \$\begingroup\$ @Peter Well, by readable I mostly meant "I don't have to horizontally scroll," but I clarified the +++. I've been trying to tweak it (especially q, which feels somewhat wasteful), but haven't found anything solid yet. \$\endgroup\$ – Geobits Jan 27 '15 at 18:12
  • \$\begingroup\$ @PeterTaylor Due to the lexing rules of Java, +++ always resolves to ++ +. \$\endgroup\$ – FUZxxl Jan 28 '15 at 8:23
  • \$\begingroup\$ @FUZxxl, I doubt that even most Java users know that, and there are lots of people on this site who don't know Java. \$\endgroup\$ – Peter Taylor Jan 28 '15 at 8:39
  • 1
    \$\begingroup\$ Using indexOf with offset instead of lastIndexOf should cut 1 byte (see my javascript answer) \$\endgroup\$ – edc65 Jan 28 '15 at 12:05
3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ How about you define g y=q(minimum.(map l)$y)$y (are the parentheses around map l really required?) and then f=g.concat.q 1.group.sort.concatMap inits.tails? \$\endgroup\$ – FUZxxl Jan 29 '15 at 13:54
  • 1
    \$\begingroup\$ Using >>= instead of concatMap, i.e. f x=p$concat$q 1$group$sort$(tails x>>=inits) saves 2 bytes. Why the Data.Ord import? \$\endgroup\$ – nimi Jan 30 '15 at 19:38
  • 1
    \$\begingroup\$ The parentheses in q are unnecessary, since you can write filter$(==)k.l, as are the last $ and the spaces before the ys in p. You can also remove the semicolons after the imports (Data.Ord seems indeed unnecessary). \$\endgroup\$ – Zgarb Jan 31 '15 at 15:41
  • \$\begingroup\$ Leksah compiler does not accept $ followed by a non-space. It will shave of some bytes, but is it in the language spec? \$\endgroup\$ – RobAu Feb 1 '15 at 10:43
  • 1
    \$\begingroup\$ GHC will accept it. \$\endgroup\$ – Zgarb Feb 1 '15 at 10:51
3
\$\begingroup\$

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 = #/.~)@(]\) ]
    
\$\endgroup\$
2
\$\begingroup\$

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]]
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ You don't need to explicitly define $j=0. Ahead, you have substr($s,$j++,$i). Without defining $j, you can rewrite this to substr($s,0+$j++,$i) and you save 2 bytes. Why is that? Well, the first time, $j will be null. And you will effectively be passing null to substr, which I don't think that will work well. Using 0+$j++ will convert the null to 0. If you see that it isn't needed, go ahead without it and just remove the $j=0 part. \$\endgroup\$ – Ismael Miguel Jan 28 '15 at 11:05
  • \$\begingroup\$ Tried that; it doesn't work because PHP doesn't have strong scoping, so $j is not cleared and reinitialised for each iteration of the while() loop. So while it's null (and hence would be converted to 0 by a $j++ call) the first time around, on future iterations of the outer loop it's left at the value it was before. It's not so much initialising as resetting. Thanks for the suggestion though :-) \$\endgroup\$ – Stephen Jan 28 '15 at 11:30
  • \$\begingroup\$ Here I offer you a 141 bytes long solution: function f($s){$l=strlen($s);while(!$a&&++$i<$l)for($j=0;$j<$l;)($b=substr($s,$j++,$i))&(strpos($s,$b)==strrpos($s,$b)&&($a[]=$b));return$a;} Changes: Removed ALL your ||1, used the bitwise & (AND) instead of && in one place, moved the $j<$l&&[...] part outside the for (saving 2 bytes) and removed some unnecessary parenthesys. \$\endgroup\$ – Ismael Miguel Jan 28 '15 at 11:48
  • 1
    \$\begingroup\$ One 134 bytes long gift for you: function f($s){$l=strlen($s);while(!$a&&++$i<$l)for($j=0;$j<$l;)strpos($s,$b=substr($s,$j++,$i))==strrpos($s,$b)&&($a[]=$b);return$a;} Changes made to the previous code: moved the $b=substr($s,$j++,$i) into strpos($s,$b) making it strpos($s,$b=substr($s,$j++,$i)), removed more unecessary parenthesys and removed the unneeded &. \$\endgroup\$ – Ismael Miguel Jan 28 '15 at 11:57
  • 1
    \$\begingroup\$ Managed a little more chopping :-) substr($s,$j++,$i) returns "" when $j reaches the length of the string, and false thereafter, so that assignment can also serve as the loop conditional break. Then there's only one use of $l remaining, so that can be consolidated as well. \$\endgroup\$ – Stephen Jan 28 '15 at 12:28
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ you can put q = length somewhere and use q, shaves off some bytes \$\endgroup\$ – RobAu Jan 29 '15 at 12:38
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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"].)

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Gray area, it should print "", but you print nothing. \$\endgroup\$ – Jakube Jan 27 '15 at 15:45
  • 1
    \$\begingroup\$ @Jakube "The exact formatting of the output is flexible" \$\endgroup\$ – KSFT Jan 27 '15 at 15:45
  • \$\begingroup\$ But you have no output at all. \$\endgroup\$ – Jakube Jan 27 '15 at 15:46
  • 2
    \$\begingroup\$ @Jakube The output is the empty string, just like it's supposed to be. I just don't have quotes around it. \$\endgroup\$ – KSFT Jan 27 '15 at 15:47
  • 1
    \$\begingroup\$ @Jakube I'll allow this, since the empty string is a special case anyway. \$\endgroup\$ – Zgarb Jan 27 '15 at 16:23
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.