Minimal Fresh Substrings

Question

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,,
ACABCACBDDABADD  A,C,AB,B,CAC,ACB,CB,BD,D,DA,ABA,BA,AD,,

The empty items are not mandatory.

Answer 1

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!

Answer 2

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

Answer 3

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")));
        Console.WriteLine(string.Join(",", f("ACABCACBDDABADD")));

        Console.ReadLine();
    }
}

Answer 4

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

Answer 5

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:
      ḟ     -   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"]

Answer 6

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>

Answer 7

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

Answer 8

Ruby, 77 bytes

->s,*a{s.scan(""){a<<(1..$'.size).map{$'[..._1]}.find{!($`+_1)[..-2][_1]}}
a}

Attempt This Online!

Answer 9

Japt, 18 bytes

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

Try it

Outputs null when there are no fresh substrings

Explanation:

¬Ë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

Answer 10

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