Thanks @NathanMerrill for allowing me to post this! The following is entirely his wording from this sandbox post (deleted):

We define a "Fresh" substring as a substring that is different from any other substring that starts earlier.

For example, if I take the string "abababc" and split it: ["ab","ab","a","bc"], the first and the last substring are fresh, but the middle two are not, because they can be found earlier in the string.

For this challenge, you need create a list of the smallest possible fresh substrings for each position in the string. If there are no fresh substrings, output and empty list or empty string, etc.

For example, if you were passed "ABABCBA", you should return ["A","B","ABC","BC","C"].

Test Cases:

ABABCBA          A,B,ABC,BC,C,   // ABC instead of AB because there is an AB earlier in the string
AAAAAAA          A,,,,,,
ABCDEFG          A,B,C,D,E,F,G

The empty items are not mandatory.

  • 1
    \$\begingroup\$ Is this case sensitive i.e. in Aa can we return A,a or A? If there are no fresh substrings, then it shouldn't be included in the list.: Can we have an empty item at that position in the list? \$\endgroup\$ Jun 9, 2017 at 15:02
  • \$\begingroup\$ Typo in test case ABCDEEFG -> ABCDEFG? \$\endgroup\$ Jun 9, 2017 at 15:16
  • \$\begingroup\$ I think you have a few more typos in your tests, I'll post my answer and show the results. Though I might have made a mistake. \$\endgroup\$ Jun 9, 2017 at 15:18
  • \$\begingroup\$ @JonathanAllan D is where you believe DD to be: smallest possible fresh substrings for each position in the string \$\endgroup\$ Jun 9, 2017 at 15:46
  • 2
    \$\begingroup\$ A,C,AB,B,CAC,ACB,CB,BD,D,DA,ABA,BA,AD for the last test case CBDis greater as CB and CB is not earlier in the string \$\endgroup\$ Jun 9, 2017 at 17:22

10 Answers 10


PHP, 141 bytes


Try it online!

  • 1
    \$\begingroup\$ All cleared up - this implementation is how it should be. \$\endgroup\$ Jun 9, 2017 at 17:00
  • \$\begingroup\$ @JonathanAllan Come on with your I assume python answer \$\endgroup\$ Jun 9, 2017 at 17:07
  • \$\begingroup\$ ...nope Jelly, was tricky - probably missed a trick or two though! \$\endgroup\$ Jun 9, 2017 at 17:34

Haskell, 105 103 88 81 79 bytes

-15 24 bytes (!) thanks to user1502040

import Data.List
f s=[a|a:_<-zipWith(\\)<*>scanl(++)[]$map(tail.inits)$tails s]

Try it online!

t gets a list of lists of all of the substrings starting from each position.

f builds up that list using scanl, so at index i we have a list of all of the substrings possible before index i. At each index, we take the set difference between the substrings calculated in t and those made illegal by f, to get the legal substrings at that index.

The lists are guaranteed to be sorted by length, so we can finally just take the first item if it exists. It skips empty items, as they are "not mandatory" per the spec.

Still learning Haskell, so I'm sure I've done something odd somewhere. The map head(filter(>[]) seems especially verbose to say "take the first item if exists, else nothing."

  • 1
    \$\begingroup\$ You can use a list comprehension instead of map head$filter(>[]). Something like [x|x:_<-myList]. \$\endgroup\$ Jun 9, 2017 at 20:48
  • \$\begingroup\$ and you can combine the two maps in the definition of t. \$\endgroup\$ Jun 9, 2017 at 20:50
  • \$\begingroup\$ Thanks @user1502040! I didn't realize you could filter by pattern in a list comprehension like that \$\endgroup\$ Jun 9, 2017 at 21:20
  • 1
    \$\begingroup\$ You can compress the whole thing into one line with a little point-free magic: f s=[a|a:_<-zipWith(\\)<*>scanl(++)([])$map(tail.inits)$tails s] \$\endgroup\$ Jun 9, 2017 at 21:31
  • \$\begingroup\$ Nice. certain language constructs (<*>) can seem pretty obscure until I see such a useful example \$\endgroup\$ Jun 9, 2017 at 21:38

C#, 175 158 bytes

s=>{int i=0,j,l=s.Length;var a=new string[l];for(;i<l;++i)for(j=0;j<l-i;){var t=s.Substring(i,++j);if(!s.Substring(0,i).Contains(t)){a[i]=t;break;}}return a;}

Full/Formatted Version:

using System;

class P
    static void Main()
        Func<string, string[]> f = s =>
            int i = 0, j, l = s.Length;
            var a = new string[l];

            for (; i < l; ++i)
                for (j = 0; j < l - i;)
                    var t = s.Substring(i, ++j);
                    if (!s.Substring(0, i).Contains(t))
                        a[i] = t;

            return a;

        Console.WriteLine(string.Join(",", f("ABABCBA")));
        Console.WriteLine(string.Join(",", f("AAAAAAA")));
        Console.WriteLine(string.Join(",", f("ABCDEFG")));
        Console.WriteLine(string.Join(",", f("ABDBABDAB")));
        Console.WriteLine(string.Join(",", f("ACABCACBDDABADD")));


Python 3, 136 bytes

for x in range(a):
 while n[x:i]in l or n[x:i]in n[:i-1]:
  if i>a:x=i;break

Try it online!

Includes the empty items

  • \$\begingroup\$ @JörgHülsermann I think it is fixed now \$\endgroup\$
    – ovs
    Jun 9, 2017 at 17:11
  • 1
    \$\begingroup\$ Works in my opinion \$\endgroup\$ Jun 9, 2017 at 17:18

Jelly,  19  17 bytes


A monadic link accepting a list of characters and returning a list of lists of characters.

Try it online! (the footer formats the list separating it with commas so it does not get implicitly printed as the representation would be smashed together).


;\0;Ṗ - Link 1, offset prefixes: list  e.g. [["x","xy","xyz"],["y","yz"],["z"]]
 \    - cumulative reduction with:
;     -   concatenation                     [["x","xy","xyz"],["x","xy","xyz","y","yz"],["x","xy","xyz","y","yz","z"]]
  0;  - prepend a zero                    [0,["x","xy","xyz"],["x","xy","xyz","y","yz"],["x","xy","xyz","y","yz","z"]]
    Ṗ - pop (head to penultimate)         [0,["x","xy","xyz"],["x","xy","xyz","y","yz"]]

ṫJ;\€µḟ"ÇZḢ - Main link: list of characters  e.g. "ABABC"
 J          - range of length                     [1,2,3,4,5]
ṫ           - tail                                ["ABABC","BABC","ABC","BC","C"]
   \€       - cumulative reduction for €ach with:
  ;         -   concatenation                    [["A","AB","ABA","ABAB","ABABC"],["B","BA","BAB","BABC"],["A","AB","ABC"],["B","BC"],["C"]]
     µ      - monadic chain separation, call that p
        Ç   - call last link as a monad with p - gets relevant substrings to not use (with a zero in place of an empty list for the first index)
            -                      ... that is:  [0,["A","AB","ABA","ABAB","ABABC"],["A","AB","ABA","ABAB","ABABC","B","BA","BAB","BABC"],["A","AB","ABA","ABAB","ABABC","B","BA","BAB","BABC","A","AB","ABC"],["A","AB","ABA","ABAB","ABABC","B","BA","BAB","BABC","A","AB","ABC","B","BC"]]
       "    - zip with:
      ḟ     -   filter discard                   [["A","AB","ABA","ABAB","ABABC"],["B","BA","BAB","BABC"],["ABC"],["BC"],["C"]]
         Z  - transpose                         [["A","B","ABC","BC","C"],["AB","BA"],["ABA"],["ABAB"],["ABABC"]]
          Ḣ - head                               ["A","B","ABC","BC","C"]
  • \$\begingroup\$ I love it you get the same result for the last test case \$\endgroup\$ Jun 9, 2017 at 17:40
  • \$\begingroup\$ I was also going to comment the same, but saw yours and just upvoted it :) \$\endgroup\$ Jun 9, 2017 at 17:41
  • \$\begingroup\$ We have now 4 programs that do the same for the last test case. I am not sure what the C# Answer make \$\endgroup\$ Jun 9, 2017 at 17:44

JavaScript (ES6), 81 bytes

<input oninput=o.textContent=f(this.value).join`\n`><pre id=o>


Retina, 19 18 bytes

-1 byte because empty items can be ommitted


Try it online!


!                   Print matches as newline separated list
 &`                 Consider overlapping matches
   (.+?)            Capture the shortest possible substring
        (?<!\1.+)   Enforce freshness
              .+    Scan backwards
            \1      Fail if the match appears earlier in the string
                    If matching is impossible, skip this element
  • \$\begingroup\$ Explanation requested. \$\endgroup\$
    – user58826
    Jun 9, 2017 at 18:38
  • \$\begingroup\$ Why do you need the |? \$\endgroup\$
    – Neil
    Jun 9, 2017 at 19:29
  • \$\begingroup\$ Otherwise, impossible cases are not included in the list. \$\endgroup\$ Jun 9, 2017 at 20:20
  • \$\begingroup\$ @CalculatorFeline I may have misread, but I thought you were allowed to stop once there were no more fresh substrings. \$\endgroup\$
    – Neil
    Jun 10, 2017 at 0:52

Ruby, 77 bytes


Attempt This Online!


Japt, 18 bytes

¬ËUsE å+ k@bX <EÃg

Try it

Outputs null when there are no fresh substrings


¬ËUsE å+ k@bX <EÃg
¬                  # Split the input into an array of characters
 Ë                 # For each index E:
  UsE              #  Get the suffix of the input with length E
      å+           #  Get all prefixes of that suffix
         k@     Ã  #  Remove the ones where:
           bX      #   The first time it appears in the input
              <E   #   Is before E
                 g #  Return the shortest one remaining

Japt, 9 bytes

ã ü@bXÃmg

Try it

ã ü@bXÃmg     :Implicit input of string U
ã             :Substrings
  ü           :Sort and group by
   @          :Passing each X through the following function
    bX        :  First index of X in U
      Ã       :End grouping
       m      :Map
        g     :  First element

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.