17
\$\begingroup\$

For the purposes of this challenge a substring \$B\$ of some string \$A\$ is string such that it can be obtained by removing some number of characters (possibly zero) from the front and back of \$A\$. For example \$face\$ is a substring of \$defaced\$

\$ de\color{red}{face}d \$

This is also called a contiguous substring.

A common substring of two strings \$A\$ and \$B\$ is a third string \$C\$ such that it is a substring of both \$A\$ and \$B\$. For example \$pho\$ is a common substring of \$photochemistry\$ and \$upholstry\$.

\$ \color{red}{pho}tochemistry\\ u\color{red}{pho}lstry \$

If we have two strings \$A\$ and \$B\$ an uncommon substring of \$A\$ with respect to \$B\$ is a third string \$C\$, which is a substring of \$A\$ and has no common substring of length 2 with \$B\$.

For example the longest uncommon substring of \$photochemistry\$ with respect to \$upholstry\$ is \$otochemis\$. \$otochemis\$ is a substring of \$A\$ and the the only nonempty common substrings of \$otochemis\$ and \$upholstry\$ are size 1 (\$o\$, \$t\$, \$h\$, and \$s\$). If we added any more onto \$otochemis\$ then we would be forced to permit a common subsring of size 2.

Task

Given two strings \$A\$ and \$B\$ output the maximum size an uncommon substring of \$A\$ with respect to \$B\$ can be. You may assume the strings will only ever contain alphabetic ASCII characters. You can assume \$A\$ and \$B\$ will always be non-empty.

This is so answers will be scored in bytes with fewer bytes being better.

Test cases

photochemistry, upholstry -> 9
aaaaaaaaaaa, aa -> 1
aaaaabaaaaa, aba -> 5
babababababa, ba -> 2
barkfied, x -> 8
barkfield, k -> 9
bakrfied, xy -> 8
\$\endgroup\$
3
  • 7
    \$\begingroup\$ Not that it affects the challenge, but the correct spelling is upholstery. \$\endgroup\$
    – Dingus
    Sep 24 at 12:27
  • 7
    \$\begingroup\$ @Dingus I fudged it a bit for the sake of the example, so that stry would be a common substring as well. \$\endgroup\$
    – Wheat Witch
    Sep 24 at 12:28
  • \$\begingroup\$ Suggest barkfied, k -> 8 that 1c B is ignored \$\endgroup\$
    – l4m2
    Sep 26 at 8:24

17 Answers 17

7
\$\begingroup\$

05AB1E, 11 8 bytes

ü«å_γO>à

Try it online! or Try all cases!

Explanation:

The longest uncommon substring is the longest sequence of adjacent length 2 substrings of \$A\$ that are not substrings of \$B\$.

ü«        # length 2 subtrings of A
  å       # for each substring: is it a substring of B?
   _      # logical negation
    γ     # split into list of equal adjacent elements
     O    # sum each section
      >   # increment each sum
       à  # take the maximum
\$\endgroup\$
1
  • \$\begingroup\$ You beat me to it. I had ŒéʒŒ2ùå_P}θg, where the Œ2ù could be golfed to your ü«. +1 from me. The _P could alternatively also be O_ or à_. \$\endgroup\$ Sep 24 at 12:30
6
\$\begingroup\$

Python 3, 58 bytes

f=lambda a,b,s=1:a>''and+max(f(a[1:],b,a[:2]in b or-~s),s)

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ and here I am struggling with 1+max((len(list(g))for k,g in itertools.groupby(a[i:i+2]in b for i in range(len(a)))if not k),default=0) \$\endgroup\$
    – Stef
    Sep 27 at 14:18
5
\$\begingroup\$

Jelly,  11 10  9 bytes

-1 using ovs's observation.

;Ɲẇ€ṣ1ẈṀ‘

Try it online!


10 byter

Ẇ;ƝẇƇ¥ÐḟṪL

Try it online!

How?

Ẇ;ƝẇƇ¥ÐḟṪL - Link: A, B
Ẇ          - sublists of A (from shortest to longest)
      Ðḟ   - filter discard those for which:
     ¥     -   last two links as a dyad, f(substringOfA, B):
 ;Ɲ        -     length 2 sublists of substringOfA
    Ƈ      -     keep those (pairs) for which:
   ẇ       -       is this pair a sublist of B?
        Ṫ  - tail -> longest uncommon substring
         L - length
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 63 bytes

Expects (B)(A).

b=>g=([c,...a])=>a+a&&Math.max(g(a)-1,g=!b.match(c+a[0])*-~g)+1

Try it online!

Commented

b =>             // main function taking the 2nd string b
g = ([           // g = recursive function taking the 1st string as:
  c,             //   c = next character
  ...a           //   a[] = array of remaining characters
]) =>            //
  a + a &&       // stop if a[] is empty (and return a zero'ish value)
  Math.max(      // otherwise, take the maximum of:
    g(a) - 1,    //   - the result of a recursive call, minus 1
    g =          //   - the updated value of g, which is:
      !b.match(  //     - 0 if b contains c + a[0]
        c + a[0] //     - g + 1 otherwise
      )          //   NB: all recursive calls have already been processed
      * -~g      //   when this part of the code is reached; so it's OK
                 //   to re-use g as a counter (initially zero'ish)
  )              // end of Math.max()
  + 1            // increment the result to make it 1-indexed
\$\endgroup\$
3
\$\begingroup\$

Retina, 33 32 bytes

(?=(..).*¶.*\1|.*$).
;¶
P`.+
\G.

Try it online!

-1 thanks to Neil.

Takes the strings \$A\$ and \$B\$ separated by a line feed for the input.

First, a Replace stage looks for each character in \$A\$ that when combined with the next character forms a pair that can be found in \$B\$ ((..).*¶.*\1 in the lookahead), as well as every character of \$B\$ (.*$ in the lookahead). Each of those characters is replaced by a semicolon followed by a line feed. This breaks \$A\$ into pieces that are uncommon with respect to \$B\$ and \$B\$ into individual characters, except with ; in place of the last character of each piece. Each piece is on a separate line.

Next, a Pad stage matches each whole line, and pads all of them to the longest length present.

Finally, a Count stage matches each character in the first line (because \G makes the matches have to be consecutive, and . does not match line feeds), and produces the number of such characters.

\$\endgroup\$
1
  • \$\begingroup\$ Last line can be \G. to save a byte. \$\endgroup\$
    – Neil
    Oct 3 at 8:21
2
\$\begingroup\$

Python 3, 80 bytes

f=lambda b,a,*r:{*zip(a,a[1:])}&{*zip(b,b[1:])}and f(b,*r,a[1:],a[:-1])or len(a)

Try it online!

Yes! Longest continuous substring again.

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

Japt, 13 bytes

Just can't seem to do better than 13.

ä@VèZÃôÎmÊÍÌÄ

Try it

ã2 ô!øV ñÊÌÊÄ

Try it

ä@VèZÃôÎmÊÍÌÄ     :Implicit input of strings U & V
ä                 :Consecutive pairs of U
 @                :Map each Z
  VèZ             :  Count the occurrences of Z in V
     Ã            :End map
      ô           :Split on elements with
       Î          :  A truthy sign (i.e., 1)
        m         :Map
         Ê        :  Length
          Í       :Sort
           Ì      :Last element
            Ä     :Add 1
ã2 ô!øV ñÊÌÊÄ     :Implicit input of strings U & V
ã2                :Substrings of U of length 3
   ô              :Split on elements
    !øV           :  Contained in V
        ñ         :Sort by
         Ê        :  Length
          Ì       :Last element
           Ê      :Length
            Ä     :Add 1
\$\endgroup\$
2
\$\begingroup\$

R, 156 107 105 99 bytes

Or R>=4.1, 85 bytes by replacing two function appearances with \s.

function(x,y,r=rle(!sapply((1:nchar(x))[-1],function(k)grepl(substr(x,k-1,k),y))))max(0,r$l[r$v])+1

Try it online!

Port of @ovs's answer.

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

Jelly, 12 bytes

ẆẆḊƇẇ€SʋÐḟẈṀ

Try it online!

How it works

ẆẆḊƇẇ€SʋÐḟẈṀ - Main link. Takes A on the left, B on the right
Ẇ            - All contiguous substrings of A
       ʋÐḟ   - Keep substrings S for which the dyadic link f(S, B) is 0:
 Ẇ           -   Substrings of S
  ḊƇ         -   Remove singleton lists
     €       -   Over each substring:
    ẇ        -     Is B a contiguous substring?
      S      -   Sum
          ẈṀ - Get the maximum length
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 18 bytes

⟨s{s₂ᶠ¬{∋~s}}⟩ᶠlᵐ⌉

Takes a list containing strings \$A\$ and \$B\$ as input; produces the longest length as output. Try it online!

Explanation

Implements the spec pretty directly:

⟨            ⟩      "Sandwich" construction:
 s                  The output is a substring (C) of the first string in the input (A)
  {         }       which satisfies this predicate with respect to the second string (B):
   s₂ᶠ               The list of all length-two substrings of C
      ¬{   }         does not satisfy this predicate:
        ∋             There exists an item in the list
         ~s            which is a substring of B
             ᶠ     Find all substrings that satisfy the sandwich predicate
              lᵐ   Length of each
                ⌉  Maximum
\$\endgroup\$
1
\$\begingroup\$

Pip, 19 bytes

U#MX J(_.BNIbMPa)^0

Takes the two strings as command-line arguments. Try it here! Or, here's a 20-byte version in Pip Classic: Try it online!

Explanation

Based on ovs's 05AB1E answer:

U#MX J(_.BNIbMPa)^0
             MPa     Map this function to each pair of characters in a:
       _.B            Concatenate them together
          NIb         Return 1 if that string is not in b, 0 if it is
     J(         )    Join the resulting list of 1s and 0s into a single string
                 ^0  Split it on 0s
  MX                 Take the maximum (i.e. the longest run of 1s)
 #                   Get its length
U                    Increment
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 14 bytes

K'2lv∑⁰vca¬;tL

Try it Online!

A bit messy.

K              # Substrings
 '         ;   # Filtered by...
         a¬    # None of...
  2lv∑         # Substrings of length 2
       vc      # Are contained in...
      ⁰        # The second input
            t  # Get the last (and longest) element
             L # Get its length
\$\endgroup\$
1
\$\begingroup\$

Attache, 37 bytes

${#Last[{_&Has\`@&1\y==[]}\x]}:Slices

Try it online!

Explanation

${#Last[{_&Has\`@&1\y==[]}\x]}:Slices
${                           }           a function taking inputs x and y
                              :Slices    ...where x = Slices[x] and y = Slices[y]
        {                }\x             all members _ of x where
                   \y                     |the elements of y which
               `@&1                       | |have a char at index 1 (i.e., length >= 2)
         _&Has\                           | |and are contained in _
                     ==[]                 |is the empty list
   Last[                    ]            obtain the last such member
  #                                      and return its length

Golfing Process

41 bytes: ${#({None[_&Has,{#_>1}\y]}\x)[-1]}:Slices

41 bytes: ${#Last[{None[_&Has,{#_>1}\y]}\x]}:Slices

40 bytes: ${#Last[{None[_&Has,{_@1}\y]}\x]}:Slices

39 bytes: ${#Last[{None[_&Has,`@&1\y]}\x]}:Slices

38 bytes: ${#Last[{#(_&Has\`@&1\y)<1}\x]}:Slices

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

K (ngn/k), 38 bytes

{#*((1&/^(2'y)?2')')#,/(''|1+!#x)[;x]}

Try it online!

Takes A as x and B as y.

  • ,/(''|1+!#x)[;x] generate all substrings of A, with the longest first
  • (...)# filter, keeping only those items where (...) has 1s
    • ((...)') apply the code in (...) to each item in the list being filtered
    • 2' take 2-length substrings of the current item
    • (2'y)? retrieve their indices in the 2-length substrings of B (returning 0N (null) if it is not present)
    • 1&/^ keep items where none of their 2-length substrings are present in B
  • #* return the length of the first (longest) uncommon substring
\$\endgroup\$
0
\$\begingroup\$

Python 3, 144 124 bytes

Naive approach, much room for golfing.

lambda a,b,l=len,r=range:max(l(c)for c in(a[x:y]for y in r(l(a)+1)for x in r(y))if all(c[n:n+2]not in b for n in r(l(c)-1)))

Try it online!

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

Charcoal, 18 bytes

I⊕L⌈⪪⭆Φθκ¬№η⁺§θκι0

Try it online! Link is to verbose version of code. Explanation: Based on @ovs' approach.

       θ            Input A
      Φ             Filter out
        κ           First character
     ⭆              Map over characters and join
             §θκ    Previous character
            ⁺       Concatenated with
                ι   Current character
         ¬№         Is not found in
           η        Input B
    ⪪            0  Split on `0`s
   ⌈                Longest string of `1`s
  L                 Length
 ⊕                  Incremented
I                   Cast to string
                    Implicitly print
\$\endgroup\$
0
\$\begingroup\$

C++ (gcc), 119 bytes 116 bytes

int f(char*a,char*b){char*c=b,s=0,l=0;for(;a[1];*a++?l=l>++s?l:s:0)for(b=c;b[1];)*a-*b++|a[1]-*b?:s=*a=0;return-~l;}

Try it online!

I used ovs' characterization of longest uncommon substring as the longest sequence of adjacent length 2 substrings of \$A\$ that are not substrings of \$B\$ (plus 1).

I only use C++98. The function takes two C-strings as input and modifies the first one. I chose not to abuse the ?: feature in gcc, but that would save at least 1 byte. Following ceilingcat's comments, I guess it doesn't hurt to use non-standard code (using ?:, UB with bitwise OR |). This saves 3 bytes.

Explanation

int f(char* a, char* b) {               // Take two C-strings as input
  char* c = b;                          // Remember the start of b
  char s = 0;                           // Current sequence length
  char l = 0;                           // Longest sequence length

  for (; a[1]; ++a) {                   // Iterate until before last character
    for (b = c; b[1];) {                // Similar
      if (*a != *b++ or a[1] != *b) {   // Compare pairs of characters
      }
      else {
        s = 0;                          // Reset current sequence length
        *a = 0;                         // Flag to indicate sequence reset
      }
    }
    if (*a) {                           // Check if sequence is reset
      ++s;                              // Increment current sequence length
      l = l > s ? l : s;                // Update maximal sequence length
    }
  }
  return l + 1;                         // Increment to get substring length
}
\$\endgroup\$
2
  • \$\begingroup\$ @ceilingcat, using bitwise OR | raises a warning, unsequenced modification. Is there a guarantee in gcc for this? Thanks for the -~l tip, I saw that in another submission but didn't know what it did ^^ \$\endgroup\$
    – Isaac Ren
    Oct 2 at 12:08
  • 1
    \$\begingroup\$ I think it depends on how strict you want to be. Many of us don't mind UB or unportability. \$\endgroup\$
    – ceilingcat
    Oct 2 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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