Longest Uncommon Substring

Question

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 code-golf 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

Answer 1

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

Answer 2

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!

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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!

Answer 16

Charcoal, 18 bytes

Ｉ⊕Ｌ⌈⪪⭆Φθκ¬№η⁺§θκι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
  Ｌ                 Length
 ⊕                  Incremented
Ｉ                   Cast to string
                    Implicitly print

Answer 17

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
}