# Minimal Fresh Substrings

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
ABDBABDAB        A,B,D,BA,ABDA,BDA,DA,,


The empty items are not mandatory.

• 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? Jun 9, 2017 at 15:02
• Typo in test case ABCDEEFG -> ABCDEFG? Jun 9, 2017 at 15:16
• 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. Jun 9, 2017 at 15:18
• @JonathanAllan D is where you believe DD to be: smallest possible fresh substrings for each position in the string Jun 9, 2017 at 15:46
• 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 Jun 9, 2017 at 17:22

# PHP, 141 bytes

for($r=[];$i<$l=strlen($a=$argn);$i++)for($t=1;$t;$t*=$t<$l)in_array($s=substr($a,$i,$t),$r)|strpos($a,$s)<$i?$t++:$r[]=$s.$t="";print_r($r);


Try it online!

• All cleared up - this implementation is how it should be. Jun 9, 2017 at 17:00
• @JonathanAllan Come on with your I assume python answer Jun 9, 2017 at 17:07
• ...nope Jelly, was tricky - probably missed a trick or two though! 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."

• You can use a list comprehension instead of map head$filter(>[]). Something like [x|x:_<-myList]. Jun 9, 2017 at 20:48 • and you can combine the two maps in the definition of t. Jun 9, 2017 at 20:50 • Thanks @user1502040! I didn't realize you could filter by pattern in a list comprehension like that Jun 9, 2017 at 21:20 • 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] Jun 9, 2017 at 21:31
• Nice. certain language constructs (<*>) can seem pretty obscure until I see such a useful example 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;
break;
}
}

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

}
}


# Python 3, 136 bytes

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


Try it online!

Includes the empty items

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

# Jelly,  19  17 bytes

;\0;Ṗ
ṫJ;\€µḟ"ÇZḢ


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

### How?

;\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:
Z  - transpose                         [["A","B","ABC","BC","C"],["AB","BA"],["ABA"],["ABAB"],["ABABC"]]

• I love it you get the same result for the last test case Jun 9, 2017 at 17:40
• I was also going to comment the same, but saw yours and just upvoted it :) Jun 9, 2017 at 17:41
• We have now 4 programs that do the same for the last test case. I am not sure what the C# Answer make Jun 9, 2017 at 17:44

## JavaScript (ES6), 81 bytes

f=(s,t=0,u=t+1,v=s.slice(t,u))=>s.indexOf(v)<t?s[u]?f(s,t,u+1):[]:[v,...f(s,t+1)]
<input oninput=o.textContent=f(this.value).join\n><pre id=o>

# Retina, 19 18 bytes

-1 byte because empty items can be ommitted

!&(.+?)(?<!\1.+)


Try it online!

Explanation:

!                   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

• Explanation requested.
– user58826
Jun 9, 2017 at 18:38
• Why do you need the |?
– Neil
Jun 9, 2017 at 19:29
• Otherwise, impossible cases are not included in the list. Jun 9, 2017 at 20:20
• @CalculatorFeline I may have misread, but I thought you were allowed to stop once there were no more fresh substrings.
– Neil
Jun 10, 2017 at 0:52