Cancel strings to make them short

Question

Overview

You will be given a list of strings. If any two elements are equal, you can delete both of them. If one element a is a substring of element b, you can delete a and split b into two parts, having excluded a from it.

For example, below are all legal operations:

["a", "a"] -> []
["cash", "as"] -> ["c", "h"]
["cash", "ca"] -> ["sh"]

Note that if the substring is a prefix / a suffix of the other string then you only end up with 1 element instead of 2.

Furthermore, if a substring occurs more than once in a longer string, it can be broken at either point.

["tester", "t"] -> ["ester"] or ["tes", "er"]

Objective

Given a list of of strings, reduce all the strings such that the longest remaining string is of minimum length. Your goal is to output this length.

Rules

• All strings will be lower case and will contain only letters a-z with no spaces or any other characters.
• There will be between 0-100 strings
• Each string will be 1-100 characters long

Test Cases

[] -> 0
["a"] -> 1
["a", "a"] -> 0
["a", "a", "a"] -> 1
["ab", "a"] -> 1
["cat", "a", "at"] -> 1
["cat", "t", "at"] -> 1
["heart", "hear", "bear", "art", "he", "b", "h"] -> 0
["heart", "ear", "h", "t"] -> 0
["heart", "ear"] -> 1
["heart", "cart", "mart", "art"] -> 4
["a", "abcde", "bcde", "cde", "de", "e"] -> 1
["element", "e"] -> 4
["element", "e", "e"] -> 2
["fastest", "t", "fas", "est"] -> 0
["lovely", "l", "love"] -> 1
["fastest", "t", "fastes"] -> 0
["aaaaaaa", "a", "a", "a", "a", "a", "a", "a"] -> 0
["cabababababa", "bab", "caba", "ababa"] -> 0
["baby", "b", "aby"] -> 0

Worked example

["heart", "hear", "bear", "art", "he", "b", "h"]
["heart", "ear", "bear", "art", "he", "b"]
["heart", "ear", "ear", "art", "he"]
["heart", "art", "he"]
["art", "art"]
[]

Code golf rules / scoring.

• Neil: What's a legal result for operating on ["element", "e"]?
• Ted: @KevinCruijssen I've added a worked example for that test case
• Jonathan Allan: ["cat", "t", "at"] -> 0 - should that be 1?
• M--: Can you explain these ["element", "e"] -> 4 and ["element", "e", "e"] -> 2? I understand the first one, but I dunno how we go from 4 (i.e. lmnt) to 2.
• Jonathan Allan: ["a", "abcde", "bcde", "cde", "de", "e"] should also be 1

Answer 1

Charcoal, 67 bytes

⊞υAFυFLιFΦLι−μκF⌕A§ικ§ιλ⊞υ+Φι∧−ξκ−ξλΦ⟦...§ικμ✂§ικ+μL§ιλ⟧νI⌊Eυ∧Lι⌈EιLλ

Try it online! Link is to verbose version of code. Explanation:

⊞υAFυ

Traverse all possible reductions starting from the input.

FLιFΦLι−μκ

Select all pairs of strings in the current list.

F⌕A§ικ§ιλ

Loop over all possible break points.

⊞υ+Φι∧−ξκ−ξλΦ⟦...§ικμ✂§ικ+μL§ιλ⟧ν

Remove the two strings from the list and add the prefix and suffix (where not empty).

I⌊Eυ∧Lι⌈EιLλ

Output the minimum maximum length.

• Ted: This seems to fail the first test case although I may be inputting it wrong
• Neil: @Ted No, it's a bug in the version of Charcoal on TIO; [[]] doesn't input correctly. [[],[]] (adding a second dummy input) should work.

Answer 2

JavaScript (ES6), 177 bytes

f=(a,s=m=a)=>a.map((p,i)=>p&&a.map((q,j)=>i-j&&q.replace(RegExp(p,'g'),(_,k)=>f(b=[...a],b[i]=q.slice(b[j]=q.slice(k+s[i]),k)))),M=Math.max(...s=a.map(s=>s.length)),M>m?0:m=M)|m

Try it online!

Commented

f = ( // f is a recursive function taking:
 a, // a[] = input array
 s = // s = variable reserved in this scope
 m = a // m = the minimum value we're looking for,
) => // initially NaN'ish
a.map((p, i) => // for each word p at index i in a[]:
 p && // abort if p is empty
 a.map((q, j) => // for each word q at index j in a[]:
 i - j && // abort if i = j
 q.replace( // search in q ...
 RegExp(p, 'g'), // ... all occurrences of p
 (_, k) => // for each match at position k,
 f( // do a recursive call:
 b = [...a], // with b[] = copy of a[] where:
 b[i] = q.slice( // b[i] = string before the match
 b[j] = q.slice( // b[j] = string after the match
 k + s[i] // using s[i] for the length of p
 ), // b[j] is zero'ish and can therefore
 k // be used as the 1st argument of the
 ) // other slice()
 ) // end of recursive call
 ) // end of replace()
 ), // end of inner map()
 M = Math.max( // M is the maximum value in:
 ...s = a.map(s => // the array s[] which contains:
 s.length // the lengths of the strings in a[]
 ) // end of map()
 ), // end of Math.max() (-∞ if a[] is empty)
 M > m ? 0 // do nothing if M > m
 : m = M // otherwise, update m to M
) // end of outer map()
| m // return m coerced to an integer (-∞ → 0)

Answer 3

Nekomata, 22 bytes

w{ĕd{ĕ;;$}=¿ÐfN,}ØcŞ#å

Attempt This Online!

Extremely slow for long inputs.

w{ĕd{ĕ;;$}=¿ÐfN,}ØcŞ#å
w{ } Loop until failure:
 ĕ Take one item out of the input
 d{ } Apply the following to the original input:
 ĕ Take another item out of it
 ;; Split it into three parts
 $ Swap the last part and the middle part
 = Check if the middle part equals to the first taken item
 ¿Ð If so, pair the two other parts into a list
 fN Remove empty lists
 , Join it with the remaining input
 Øc Prepend an empty list (so that there is always a longest item)
 Ş Find the longest item
 # Get its length
 å Find the minimal possible result

If there are multiple smallest lengths, Nekomata will output the same result multiple times. You can add the -1 flag to output only the first one.