# One pair or fewer

Given a list of positive integers, give the longest contiguous sublist which contains at most 1 pair of identical items. In the case of a tie return any of the solutions.

This is so the goal is to minimize your source code with answers being scored in bytes.

## Test cases

[] -> []
[1,2,3] -> [1,2,3]
[1,2,2,3] -> [1,2,2,3]
[2,2,3,2,4] -> [2,3,2,4]
[1,2,1,3,2] -> [2,1,3,2]
[1,2,3,1,4,1,2,3,4,5,1] -> [1,2,3,4,5,1]
[1,2,3,2] -> [1,2,3,2]

• I don't understand, is this submission asking us to rewrite the filterDuplicates functions or something? Jan 30 at 12:52
• @logic It is asking you to write a program or function which takes a list of positive integers and gives the lonest contiguous sublist which contains 1 or fewer pairs of identical elements. If you have a more specific question about any of the terms I can answer it, but I don't currently know where you are struggling. Jan 30 at 12:54
• Isn't the answer ambiguous? What makes [1,2,3,1,4,1,2,3,4,5,1] -> [1,2,3,4,5,1] the correct solution? Couldn't [1,2,3,1,4,1,2,3,4,5,1] -> [4,1,2,3,4,5] also be a valid solution? Jan 31 at 12:36
• @Alderath " In the case of a tie return any of the solutions." Jan 31 at 12:36
• @WheatWizard Sorry. My bad. Sometimes my brain silently discards small pieces of instructions... Jan 31 at 12:38

# Jelly, 10 bytes

Ẇœ-QḊƊÐḟṪȯ


Try it online!

### How?

Ẇœ-QḊƊÐḟṪȯ - Link: list, A
Ẇ          - substrings (well, non-empty ones) sorted by length then left to right
Ðḟ   - filter discard those for which this is truthy:
Q       -     distinct values
œ-        -     multiset difference - remove one of each value from A
Ḋ      -     dequeue - remove one from this list if there are any
- [] is falsey
Ṫ  - tail - one of, or the, longest one
- unless A was [] in which case zero
ȯ - logical OR with A - replace that zero with []


Alternatively, Ẇœ-QLỊƲƇṪȯ.

• Nice use of Ḋ and Ðḟ - I had this 11 byter Jan 30 at 0:25
• Þ works with your 11 too, but still need the ȯ to handle the empty list unfortunately. Jan 30 at 0:57
• What is the definition of bytes in Code Golf? len(bytes("Ẇœ-QḊƊÐḟṪȯ", 'utf-8')) == 22 Jan 31 at 8:56
• @batisteo the raw source-code itself is 10 bytes, the representation above is just making use of a mapping -- Jelly's code-page, which is linked to by the "bytes" in the header. Hence counting the bytes of the Unicode characters you see above is not the source-code byte count for scoring purposes. Jan 31 at 12:11

# JavaScript (Node.js), 64 bytes

f=(a,...r)=>a[new Set(a).size+1]?f(...r,a.slice(1),a.pop()&&a):a


Try it online!

# Python 3, 58 bytes

f=lambda l,*r:len(l)>1+len({*l})and f(*r,l[1:],l[:-1])or l


Try it online!

Yet another question solved with same pattern?

• -1 on the Python one I think. Jan 29 at 9:10

# Brachylog, 1412 10 bytes

-2 bytes thanks to xash

⊇.ọtᵐ×≤2&s


Try it online!

### Explanation

We're looking for a sublist in which each element occurs only once, except that one element may occur twice.

Makes use of this very helpful tip from Unrelated String.

⊇.ọtᵐ×≤2&s
The input
⊇           Sublist (not necessarily contiguous), trying longest first
.          The result is the output
ọ         Generate a list of [element, count] pairs
tᵐ       Get the last element of each pair (list of counts)
×      Product
≤2    Is less than or equal to 2
&s  Also, the output is a contiguous sublist of the input

• 9b by checking if product of the occurrence counts is less or equal 2: Try it online!
– xash
Jan 30 at 0:13
• The &s is necessary so that the output is a contiguous sublist of the input, but that still saves 2 bytes. Thanks! Jan 30 at 4:50

# Jelly, 11 bytes

ẆµĠẈ’SỊµƇṪȯ


Try It Online!

-1 byte thanks to Jonathan Allan

ẆµĠẈ’SỊµƇṪȯ   Main Link
Ẇ             all sublists
µ     µƇ     filter
Ġ           - group indices of equal elements
Ẉ          - length of each group
’         - subtract one from each length
S        - sum of these (total number of duplicate elements)
Ị       - is this insigificant? (between -1 and 1)
Ṫ    take the last (longest) element
ȯ   logical OR; if the output is 0 (only happens if input
is []), return the input instead, which fixes [] being
output as 0

• ȯ will do the job at the end there. Jan 28 at 22:46

# Japt-h, 14 bytes

Feel like I'm missing a trick here :\

ã fÈÊÉ¶Xâ ÊÃiU


Try it

• 12? Jan 28 at 22:47
• Also 10 could work if longer sublists are at the end but not sure Jan 28 at 22:49

# Python 3, 68 bytes

f=lambda l:len(l)>1+len({*l})and max(f(l[1:]),f(l[:-1]),key=len)or l


Try it online!

f [email protected](u:q)|0:(0<$l)<[0|x<-l,y<-q,x==y]=f(init$l)!f q
f q=q
a!b|(a<$a)>(a<$b)=a|1>0=b


Try it online!

• Thanks to @Wheat Wizard for saving so many many bytes!

g : counts duplicates. -> moved to list comprehension in f by Wheat Wizard , the tricky part is here and deserves an explanation

f(u:q)|
(0<$q) list 0s for each element < compared to [0|x<-q,y<-q,x==y] list of 0s for each equal pairs in the powerset  Note that we use tail so that one potential dupe is already counted and the lists must be the same, if not there is more than 1 dupe, in that case we search.. Else we skip this and f q=q match giving the result. a!b : selects longer list. flist : if list is not ok choose from head or tail else return it • 96 Jan 30 at 0:34 • It doesn't work because 0 is a num. You can use () instead which it likes but a is shorter. Jan 30 at 0:42 • Yeah, it's an easy fix though: 80 Jan 30 at 0:53 • I think that my trick actually does not work. It fails on [1,2,3,2]. I incorrectly assumed that the solution would always start with one of the elements in the pair. Fixing it costs 5 bytes Jan 30 at 2:41 • @Wheat Wizard I managed to use the trick partially, at least I think it works Jan 30 at 5:41 # Retina 0.8.2, 78 bytes M!&r.*\d\b .*\b(\d+)(?=.*,\1\b),(.*\b(\d+)\b.*,\3\b)$2
O$^((,)|\d)+$#2
1G


Try it online! Link includes test cases. Explanation:

M!&r.*\d\b


Take all of the suffixes.

.*\b(\d+)(?=.*,\1\b),(.*\b(\d+)\b.*,\3\b)
$2  Truncate them at the second last duplicate. (Since we need this longish regex to check for two pairs/three of a kind, it turns out to be golfier to truncate the prefixes than to filter on all sublists.) O$^((,)|\d)+
\$#2


Sort by descending number of elements.

1G


Take the first.

# Ruby, 63 bytes

f=->l,s=1{l[-s]&&f[l,s+1]||l.each_cons(s).find{|q|q.uniq[s-2]}}


Try it online!

# Burlesque, 28 bytes

su<-{f:)-]g_2<=j{1==}al&&}fe


Try it online!

su           # All substrings from shortest to longest
<-           # Reverse (longest first)
{
f:          # Frequency list as (count, val) sorted by count
)-]         # Map head (get counts)
g_          # Split into head + tail
2<=         # Head is 2 or 1
j           # Swap
{1==}al     # Tails all 1s
&&          # Logical AND
}fe          # Find the first element for which


# R, 162 bytes

Or R>=4.1, 148 bytes by replacing two function occurrences with \s.

function(v,a=apply(combn(rep(seq(v),2),2),2,function(x,t=table(k<-v[x[1]:x[2]]))if(x[1]<=x[2]&all(t%in%1:2)&sum(t==2)<2)k))"if"(sum(v),a[order(-lengths(a))[1]],v)


Try it online!

I was hoping for some ingenious answer from better R golfers here, but it looks like I have to post my boring straightforward one first for some motivation.

# Factor + math.unicode, 77 bytes

[ f suffix all-subseqs [ histogram values 1 v-n Σ 2 < ] find-last nip sift ]


Try it online!

## Explanation

• f suffix ... sift Work around the fact that all-subseqs blows up on an empty input. Add f to the input and remove it with sift at the end. (This doesn't change anything since we're only adding one.)
• all-subseqs [ ... ] find-last nip Find the last/largest subsequence of the input that returns true when the given quotation is called on it.

The quotation to find-last works by taking a histogram of the input, subtracting 1 from all the counts, taking the sum, and checking whether the sum is less than two. For instance:

             ! { 2 2 3 2 4 }
histogram    ! H{ { 2 3 } { 3 1 } { 4 1 } }
values       ! { 3 1 1 }
1 v-n        ! { 2 0 0 }
Σ            ! 2
2 <          ! f


# Wolfram Language (Mathematica), 47 bytes

f[s=___,[email protected]:s,s]/;Total[[email protected]{a}-1]<2=a


Try it online!

Input and output a Sequence of values.

### Wolfram Language (Mathematica), 48 bytes

[email protected]*Select[Total[[email protected]#-1]<2&]@*Subsequences


Try it online!

Input and output a list.

import Data.List
l=length


Try it online!

Get all infixes, sort by (invalid, -length), return the first one.

# Charcoal, 40 38 bytes

≔⟦⟧ηＦθ«⊞υιＷ‹¹ΣＥυ›μ⌕υλ≔Φυμυ¿›ＬυＬη≔Ｉυη»η


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

≔⟦⟧η


Ｆθ«


Loop over the input terms.

⊞υι


Append the term to the predefined empty list.

Ｗ‹¹ΣＥυ›μ⌕υλ


While the current sublist contains more than one duplicate...

≔Φυμυ


... remove the first term from the sublist.

¿›ＬυＬη


If the sublist is longer than the longest sublist so far, then...

≔Ｉυη


... save a copy of the sublist (because we're going to push to the original, and we need to cast it to string anyway).

»η


Output the longest sublist (which we already cast to string above).

# Husk, 10 9 bytes

Edit: -1 byte thanks to Razetime

►LfoεṠ-uQ


Try it online!

►           # output the (first) element with maximum...
L          # ...length...
# ...from among:
Q  # all contiguous sublists,
fo        # filtered by:
Ṡ-    # the difference between...
u   # ...itself and unique elements of itself...
ε       # ...has length 1.

• -1: ►LfoεṠ-uQ, ε checks size of the list as well Feb 1 at 8:26
• @Razetime - Thanks! I need to re-read the docs, I guess... Feb 1 at 8:43
• @Razetime - BTW: last day to try to crack this... Feb 1 at 8:44
• oh, i see. I did not notice this thread. Feb 1 at 8:51

# JavaScript (Node.js), 79 75 bytes

f=(X,a)=>X[h=new Set([w,...x]=X).size+1]?(a=f(x),b=f(X,X.pop()),a[h]?a:b):X


Try it online!

AnttiP's idea, can't read golfing language so don't know if that's source

# JavaScript (Node.js), 89 bytes

f=(x,h,L=0,a=x.filter(y=x=>!(y[x]=h+=[y[x]])[20]&&++L),b=x[0]?f(x.slice(1)):[])=>b[L]?b:a


Try it online!

Is it usual to be 6-8x longer than golfing language or this is quite golfable?

# 05AB1E, 11 bytes

ŒʒgyÙg-!}éθ


Explanation:

Œ        # Get all sublists of the (implicit) input-list
ʒ       # Filter this list of sublists by:
g      #  Get the length of the sublist
y     #  Push the sublist again
Ù    #  Uniquify its items
g   #  Pop and push the length of this uniquified list as well
-  #  Subtract the lengths from one another
! #  Check if this is either 0 or 1 by taking the faculty, which will
#  result in [1,1,2,6,24,120,...] for [0,1,2,3,4,5,...] respectively,
#  and only 1 is truthy in 05AB1E
}é      # After the filter: sort the remaining sublists from shortest to longest
θ     # Pop and keep just the last (longest)
# (after which it is output implicitly as result)