Efficient censorship

Question

This challenge was originally posted on codidact.

---

You are a low-level censor working for the Ministry of Media Accuracy. Part of your job is to make sure that certain words don't appear in publications. Every morning you get a fresh stack of next week's newspapers and its your job to comb through them and fix any of the words that were mistakenly included. A naive censor might simply remove the entire word completely, but you know that if you remove part of the word that still prevents the word from appearing in print. So for you it is a point of pride to remove as little of the offending word as possible while still ensuring it does not appear in print.

Task

Given non-empty strings \$X\$ and \$Y\$ output the longest substring of \$X\$ which does not contain \$Y\$ as a contiguous substring

This is code-golf so the goal is to minimize the size of your source code as measured in bytes.

Test cases

For each input output pair a possible correct output is given, your output should always be the same length, but it is not necessary to reproduce these outputs exactly.

chat, cat -> chat
escathe, cat -> esathe
homology, o -> hmlgy
ccatt, cat -> cctt
aababbabab, abab -> aaabbbab
ababab, abab -> abbab
aaaaaaaa, aaa -> aa
a, a -> 

Answer 1

Python 3, 86 bytes

f=lambda s,t,i=0:s if t not in s else max([f(s[:i]+s[(i:=i+1):],t)for x in s],key=len)

Attempt This Online!

Ungolfed and commented

def f(s, t):
    if t not in s: # return s if it's valid (ie. doesn't contain t)
        return s
    return max([ # recurse on all substrings with 1 character removed
        f(
            s[:i] + s[i+1:], # s without the character at index i
            t
        )
        for i in range(len(s))
    ], key=len) # find the longest valid substring

Answer 2

Jelly, 6 bytes

ŒPwÐḟṪ

Try It Online!

Explanation

ŒPwÐḟṪ    Main Link
ŒP        Powerset (all subsequences) of the left argument
   Ðḟ     Filter where falsy:
  w       The sublist index of the right argument (0 if not found)
     Ṫ    Tail (Last Element) - powerset generates in increasing order of length

Answer 3

Vyxal, 8 bytes

ṗ'⁰c¬;ÞG

Try it Online!

      ÞG # Longest
ṗ        # Subsequence of input
 '   ;   # Which
    ¬    # Does not
   c     # Contain
  ⁰      # The other input

Answer 4

Python3, 108 bytes

lambda x,y:max(f(x,y),key=len)
f=lambda x,y,r='':[r]*(y not in r)if''==x else f(x[1:],y,r)+f(x[1:],y,r+x[0])

Try it online!

Answer 5

Retina 0.8.2, 52 bytes

+%`(.),
,$'¶$`,$1
Ar`\1.* (.+)$
O^#$`
$.&
,| .+

1G`

Try it online! Link includes test cases. Assumes that the strings don't contain commas or spaces. Explanation:

+%`(.),
,$'¶$`,$1

Generate all subsequences of the first input.

Ar`\1.* (.+)$

Delete those that contain the second input.

O^#$`
$.&

Sort the remainder in descending order of length.

,| .+

Delete the second input.

1G`

Keep only the longest subsequence.

Answer 6

Scala 3, 141 bytes

Port of @SuperStormer's Python answer in Scala.

---

Golfed version. Attempt this online!

def f(s:String,t:String):String={if(!s.contains(t))s;else{(0 until s.length).map{i=>f(s.substring(0,i)+s.substring(i+1),t)}.maxBy(_.length)}}

Ungolfed version. Attempt this online!

object Main extends App {

  def removeLongestSubstring(s: String, t: String): String = {
    if (!s.contains(t)) s
    else {
      (0 until s.length).map { i =>
        removeLongestSubstring(s.substring(0, i) + s.substring(i + 1), t)
      }.maxBy(_.length)
    }
  }

  val testCases = List(
    ("chat", "cat", "chat"),
    ("escathe", "cat", "esathe"),
    ("homology", "o", "hmlgy"),
    ("ccatt", "cat", "cctt"),
    ("aababbabab", "abab", "aaabbbab"),
    ("ababab", "abab", "abbab"),
    ("aaaaaaaa", "aaa", "aa")
  )

  for ((s, t, o) <- testCases) {
    println(s"$s $t ${removeLongestSubstring(s, t)} $o")
  }
}

Answer 7

05AB1E, 8 bytes

æéR.ΔIå≠

Try it online or verify all test cases.

Explanation:

æ         # Get the powerset of the first (implicit) input-string
 é        # Sort it by length (shortest to longest)
  R       # Reverse it, so it's sorted from longest to shortest
   .Δ     # Find the first string that's truthy for:
       ≠  #  Check that the current powerset-string does NOT
      å   #  contain
     I    #  the second input-string
          # (after which the found result is output implicitly)

The R.Δ... could alternatively be ʒ...}θ (filter, and keep last item after the filter) for the same byte-count.

Answer 8

Charcoal, 26 bytes

⊟⌈ＥΦＥＸ²ＬθΦθ﹪÷ιＸ²μ²¬№ιη⟦Ｌιι

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

      ²                     Literal integer `2`
     Ｘ                      Raised to power
        θ                   First input
       Ｌ                    Length
    Ｅ                       Map over implicit range
          θ                 First input
         Φ                  Filtered where
             ι              Outer value
            ÷               Integer divided by
               ²            Literal integer `2`
              Ｘ             Raised to power
                μ           Inner index
           ﹪     ²          Is odd
   Φ                        Filter over subsequences where
                    ι       Current subsequence
                  ¬№        Does not include
                     η      Second input
  Ｅ                         Map over remaining subsequences
                        ι   Current subsequence
                       Ｌ    Length
                         ι  Current subsequence
                      ⟦     Make into list
 ⌈                          Get a subsequence with the longest length
⊟                           Get the subsequence
                            Implicitly print

Answer 9

JavaScript (ES12), 76 bytes

Expects (Y)(X).

y=>o=g=([c,...x],s='')=>c?g(x,s+c)|g(x,s)||o:o=s.match(y)||o?.[s.length]?o:s

Attempt This Online!

Commented

y =>                // y = forbidden word
o =                 // o = output, initially not a string
g = (               // g is a recursive function taking:
  [ c,              //   c = next character from the input text
       ...x ],      //   x[] = remaining characters
  s = ''            //   s = censored text
) =>                //
c ?                 // if c is defined:
  g(x, s + c) |     //   do a 1st recursive call with c added to s
  g(x, s) ||        //   do a 2nd recursive call with s unchanged
  o                 //   eventually return o
:                   // else:
  o =               //   update o:
    s.match(y) ||   //     if s contains y
    o?.[s.length] ? //     or o is a string longer than s:
      o             //       leave o unchanged
    :               //     else:
      s             //       update o to s

Answer 10

Haskell, 161 bytes

c=concatMap
l=length
[]%y=y/=[]
x%y=(l x<l y||or(zipWith(/=)x y))&&tail x%y
r[]=[]
r(x:y)=y:map(x:)(r y)
x#0=[x]
x#n=c r$x#(n-1)
x!y=head$c(filter(%y).(x#))[0..]

Attempt This Online!

Answer 11

JavaScript (Node.js), 74 bytes

y=>g=([c,...x],s=o='')=>c?g(x,s+c)|g(x,s)||o:o=s[s.match(y)||o.length]?s:o

Attempt This Online!

Optimized from Arnauld's

JavaScript (Node.js), 76 bytes

S=>g=(T,...U)=>T.join``.match(S)?g(...U,...T.map((_,i)=>T.filter(_=>i--))):T

Try it online!

Same length as Arnauld's but worse at almost all other ways

Answer 12

Thunno 2 t, 7 bytes

ʠþlæ¹Ƈ}

Try it online!

Port of Kevin Cruijssen's 05AB1E answer.

Explanation

ʠþlæ¹Ƈ}  # Implicit input
ʠ        # Powerset of the first input
 þl      # Sort it by length
   æ  }  # Remove items which:
    ¹Ƈ   #  Contain the second input
         # Implicit output of last item

Answer 13

Pyth, 7 bytes

ef!}zTy

Try it online!

Explanation

ef!}zTyQ    # implicitly add Q
            # implicitly assign Q=eval(input()); z=input()
      yQ    # powerset of Q
 f          # filter on lambda T
  !}zT      #   z not in T
e           #   last element (longest)