17
\$\begingroup\$

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 -> 
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Hmm...is there a linear time algorithm for this? \$\endgroup\$
    – Simd
    Aug 5, 2023 at 5:40
  • 2
    \$\begingroup\$ @Simd there's a quadratic algorithm for this (build the Aho-Corasick automaton, and keep track of the longest substring ending in each state so far), but it doesn't feel like there's a linear time algorithm \$\endgroup\$ Aug 7, 2023 at 23:54

13 Answers 13

5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Vyxal, 8 bytes

ṗ'⁰c¬;ÞG

Try it Online!

      ÞG # Longest
ṗ        # Subsequence of input
 '   ;   # Which
    ¬    # Does not
   c     # Contain
  ⁰      # The other input
\$\endgroup\$
3
  • 1
    \$\begingroup\$ -1 byte if you just take the last subsequence instead of the longest, since they are generated in increasing order of length: Try It Online! \$\endgroup\$
    – hyper-neutrino
    Aug 5, 2023 at 0:35
  • 1
    \$\begingroup\$ @hyper-neutrino Due to reasons involving infinite lists, Vyxal doesn't actually output powersets in order of length - Try it Online!. Notice how it gives the wrong result for 'aababbabab', 'abab'. \$\endgroup\$
    – emanresu A
    Aug 5, 2023 at 0:52
  • 1
    \$\begingroup\$ Oh, interesting. My bad, I could've noticed that on the fourth example if I was paying any attention at all. \$\endgroup\$
    – hyper-neutrino
    Aug 5, 2023 at 2:29
1
\$\begingroup\$

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!

\$\endgroup\$
2
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 26 bytes

⊟⌈EΦEX²LθΦθ﹪÷ιX²μ²¬№ιη⟦Lιι

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

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

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.