# Longest Uncommon Substring

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.

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
• Not that it affects the challenge, but the correct spelling is upholstery. Sep 24 at 12:27
• @Dingus I fudged it a bit for the sake of the example, so that stry would be a common substring as well. Sep 24 at 12:28
• Suggest barkfied, k -> 8 that 1c B is ignored
– l4m2
Sep 26 at 8:24

# 05AB1E, 11 8 bytes

ü«å_γO>à

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
• 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 à_. Sep 24 at 12:30

# 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!

• 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)
– Stef
Sep 27 at 14:18

# Jelly,  11 10  9 bytes

-1 using ovs's observation.

;Ɲẇ€ṣ1ẈṀ‘

Try it online!

Ẇ;ƝẇƇ¥ÐḟṪ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

# 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

# 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.

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

# 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.

# 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
ã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

# R, 156107105 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.

# 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

# 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

# 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

# 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

# Attache, 37 bytes

${ } 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

# 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

# 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!

# 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
η        Input B
⪪            0  Split on 0s
⌈                Longest string of 1s
Ｌ                 Length
⊕                  Incremented
Ｉ                   Cast to string
Implicitly print

# 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
}
• @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 ^^ Oct 2 at 12:08
• I think it depends on how strict you want to be. Many of us don't mind UB or unportability. Oct 2 at 18:01