# Longest Sublist with Equal Occurrences

Given a non-empty list of integers between 1 and 9 inclusive, find the longest contiguous sublist such that the number of occurrences of each element (of the sublist) within the sublist is equal (not the number of consecutive occurrences, just the total count). You may return any non-empty subset of the solutions.

## Examples

Input                         ->  Output

1, 2, 3                           [1, 2, 3]
1, 2, 2, 3, 3, 4                  [2, 2, 3, 3]
1, 2, 3, 3, 4, 4, 3, 3, 2, 1      [3, 3, 4, 4], [3, 4, 4, 3], [4, 4, 3, 3]
1, 1, 1, 1, 1                     [1, 1, 1, 1, 1]
1, 2, 3, 2, 1                     [1, 2, 3], [3, 2, 1]
1, 2, 3, 4, 4, 3                  [1, 2, 3, 4], [3, 4, 4, 3]
3, 2, 3, 4, 4, 3                  [3, 4, 4, 3]

• this is , so the shortest code in bytes wins
• Standard Loopholes are forbidden, as usual
• I/O may be in any reasonable format. You can do I/O with a string of digits since all inputs will be between 1 and 9, for example (this is mostly to allow regex solutions if anyone can figure that out).
• This question was in the Sandbox (visible to 10k+). Imaginary brownie points for matching/beating my 8-byte Jelly solution. May 12, 2021 at 15:00

# Brachylog, 8 7 bytes

⊇.ọtᵛ&s


Try it online!

s generates all sublists of consecutive elements, though not in order of length, but in order of prefix (so [1,2,3] [1,2]  [2,3]  ). ⊇ on the other hand does generate longer sets first, but only guarantees element order, not that they are consecutive. So we check that later for +1 byte.

⊇.ọtᵛ&s  The (implicit) input                        [1,1,2,3]
⊇        has an (ordered) subset                     [1,2,3]
.       that is the output,
ọ      which elements grouped&counted by identity  [[1,1],[2,1],[3,1]]
tᵛ    have the same number of occurences.         1
&  The input                                   [1,1,2,3]
s has consecutive elements                    [1,2,3]
that is the (implicit) output.


• Before the edit, I was about to say "FWIW, identity should be ≡, but since every element is a single digit = does work too" May 12, 2021 at 15:49
• @UnrelatedString yeah, I actually intended to use proper identity, but mix the symbols up sometimes – especially if it doesn't change the output. :-)
– xash
May 12, 2021 at 15:53

# Jelly, 8 7 bytes

ẆĠẈEƊƇṪ


Try it online!

## How it works

ẆĠẈEƊƇṪ - Main link. Takes L on the left
Ẇ       - All non-empty contiguous sublists of L, longest last
ƊƇ  - Keep those sublists S for which the following is true:
Ġ      -   Group the indices of S by the elements
Ẉ     -   Length of each
E    -   All equal?
Ṫ - Get the last (i.e. the longest) element

• Wow, you're very fast at coding in Jelly! May 12, 2021 at 15:01
• also yes this is exactly the solution I had May 12, 2021 at 15:01
• @hyper-neutrino i am speed :P May 12, 2021 at 15:01

# Husk, 9 7 5 bytes

►ṠË#Q


Try it online!

-2 using the return value of Ë in max by.

-2 from Leo.

## Explanation

►ṠË#Q
Q all sublists (unsorted)
►     max by:
ṠË       all elements of the list are equal by: (if all equal, returns len+1)
#      count of occurrences in in the list

• Nice use of maxby! And you can save two more bytes with Ṡ: Try it online!
– Leo
May 13, 2021 at 0:07
• Should remind myself that combinators also work on higher order function May 13, 2021 at 2:39

# JavaScript (Node.js), 86 bytes

f=(h,...t)=>new Set(c=[],h.map(x=>c[x]=-~c[x])).size<3?h:f(...t,h.slice(1),h.pop()&&h)


Try it online!

Use Breadth-First Search, so you may avoid comparing its length.

A terrible $$\O(n\cdot2^n)\$$ time complexity. Luckly we only care about its length.

Codes for checking equal number occurrence is copied from Arnauld's answer.

# Python 3, 63 bytes

f=lambda l,*t:l*(len({*map(l.count,l)})<2)or f(*t,l[1:],l[:-1])


Try it online!

This Python answer is based on att's answer by applying BFS to it.

Comparing to JS, Python is good at creating sets, function auto bind, get length, array slicing when you are golfing.

# Scala, 84 bytes

_.tails.flatMap(_.inits)filter(l=>l.map(x=>l.count(_==x)).toSet.size<2)maxBy(_.size)


Try it in Scastie!

_.tails                //All suffixes
.flatMap(_.inits)    //All prefixes of those suffixes (all subsequences)
filter(l=>           //Keep the ones where
l.map(x=>l.count(_==x))  //The counts of all the elements
.toSet.size<2          //Has 0 or 1 distinct elements
)maxBy(_.size)       //Find the biggest such subsequence


# 05AB1E, 8 bytes

ŒʒD¢Ë}éθ


Try it online!

Œ          # all sublists of the input
ʒ   }     # filter by:
¢       #   counts of each value
D        #   in a copy of the sublist
Ë      #   are all counts equal?
é    # sort the remaining sublists by length
θ   # take the last one


Alternatively, sort first, reverse and take the first sublist that satisfies the condition:

ŒéR.ΔD¢Ë


Try it online!

# Japt-h, 10 bytes

ã kÈü üÊÊÉ


Try it

ã kÈü üÊÊÉ     :Implicit input of array
ã              :Subsections (sorted by length)
k            :Remove elements that return falsey (0)
È           :When passed through the following function
ü          :  Group by value
ü        :  Group by
Ê       :    Length
Ê      :  Length
É     :  Minus 1
:Implicit output of last element in resulting array


# Python 3, 73 bytes

f=lambda l:l*(len({*map(l.count,l)})<2)or max(f(l[1:]),f(l[:-1]),key=len)


Try it online!

# 05AB1E, 9 8 bytes

ŒʒD¢Ë}éθ


Try it online!

Œ     all sublists
ʒ     keep those such that
D     duplicate
¢     count, vectorizes
Ë     all equal
}
é     sort by length
θ     last


• two identical osabie answers May 12, 2021 at 15:33
• @Razetime this was actually created before the other one
– user100690
May 12, 2021 at 15:39
• @ophact I think I had the 8 bytes a few seconds earlier, but it is fine to keep both answers.
– ovs
May 12, 2021 at 15:47

# JavaScript (ES6), 108 bytes

Returns the rightmost solution.

a=>a.map((_,n)=>a.map((_,i)=>(b=a.slice(i,i-~n))[new Set(b.map(x=>c[x]=-~c[x],c=[])&&c).size-2+n]?o=b:0))&&o


Try it online!

### Commented

a =>                       // a[] = input array
a.map((_, n) =>          // for n = 0 to len(a) - 1:
a.map((_, i) =>        //   for i = 0 to len(a) - 1:
( b =                //     define b[] as the sub-array of length
a.slice(i, i - ~n) //     at most n + 1 starting at index i
)[                   //
new Set(           //     build a set consisting of the number of
b.map(x =>       //     occurrences of each distinct entry in b[],
c[x] = -~c[x], //     using another array c[] to keep track of
c = []         //     these counts
)                //     the set will always include 'undefined'
//     because c is never updated
&& c             //
).size             //     which is why we expect its size to be 2
- 2 + n            //     make sure that b[new Set().size - 2 + n]
]                    //     is defined (i.e. b[] is long enough and
//     the number of occurrences are all equal)
?                    //     if so:
o = b              //       update the output
:                    //     else:
0                  //       do nothing
)                      //   end of inner map()
)                        // end of outer map()
&& o                     // return o

• new Set(c=[],b.map(x=>c[x]=-~c[x]))
– tsh
May 13, 2021 at 4:03

# Python 3.8 (pre-release), 104 bytes

lambda x:max((a for i in range(len(x)+1)for j in range(i)if len({*map((a:=x[j:i]).count,a)})<2),key=len)


Try it online!

-1 thanks to @ophact

-24 thanks to @pxeger

-10 thanks to @hyper-neutrino

• Seems like <2 works instead of ==1? I'm not as proficient in python compared to js though.
– user100690
May 12, 2021 at 16:24
• dict(...) can be {**...}. But it's actually shorter counting manually: Try it online! May 12, 2021 at 16:25
• -5 on pxeger's if you map with x[i:j].count May 12, 2021 at 16:27
• Actually a Counter already has a .values() method because it's a subclass of dict, so the {**...} is unnecessary (not that it matters any more) May 12, 2021 at 16:28
• -5 using walrus and bring ophact's <2 back: tio.run/… May 12, 2021 at 16:32

# R, 1049896 95 bytes

function(L,n=seq(!L)){for(i in n)for(j in n)if(!sd(table(a<-L[i:j])+!1:2)&sum(T|1)<j-i+2)T=a;T}


Try it online!

Ugly straightforward approach. Can't wait for a nice R solution!

-6 bytes thanks to @Dominic
-1 byte thanks to @Giuseppe

• 98 bytes...? May 12, 2021 at 21:21
• The +0*1:2 trick is very clever - and you could re-use it for the 'are the items all the same' challenge... May 13, 2021 at 17:57
• Use !1:2 instead of 0*1:2 to save a byte. May 13, 2021 at 18:00

last.sortOn l.filter((<2).l.nub.map l.group.sort).(>>=tails).inits
l=length
import Data.List


Try it online!

Either Haskell is not the language for this challenge, or I'm not the Haskeller for this challenge1.

1 Yup, I know, it's the latter.

# J, 38 33 bytes

0{(1=&#[:=#/.~)\\.(\:#&>)@#&,<\\.


Try it online!

-5 thanks to xash!

• With monadic = and double \\. for less boxing: 33b
– xash
May 12, 2021 at 17:51
• Very nice. Thanks @xash. May 12, 2021 at 17:55

# JavaScript, 122 bytes

f=(n,p=t=n.length)=>n.find((e,i)=>i+p<=t&(l=n.slice(i,i+p)).every(x=>(z=m=>l.filter(w=>w==m).length)(x)==z(e)))?l:f(n,p-1)


One must marvel at the sheer length of counting the number of occurrences in a list.

A recursive function which checks all lists of length p for one satisfying the OP's conditions, and if there exists one, return it, otherwise return f(n,p-1)

Suggestions are welcome for golfing.

• Just a minor golf, but you can use w-m instead of w==m (counting the number of occurrences of not m eventually leads to the same results). May 12, 2021 at 16:53
• You can save another byte by using !some(...X-Y...) instead of every(...X==Y...). May 12, 2021 at 17:02
• @Arnauld I understand your first suggestion, but I'm not sure why your second saves another. Is it not just the same number of bytes as the first one?
– user100690
May 12, 2021 at 17:03
• !some is just as long as every, but - is shorter than ==. May 12, 2021 at 17:04

# Factor, 6358 56 bytes

[ all-subseqs [ histogram values all-eq? ] filter last ]


Try it online!

              [                          ] filter last   ! Select the last/largest..
all-subseqs                                            ! ..subsequence..
histogram values                         ! ..whose elements occur..
all-eq?                 ! ..the same number of times.


# Wolfram Language (Mathematica), 44 bytes

Last@*Select[Equal@@Counts@#&]@*Subsequences


Try it online!

Get all subsequences (ordered), select the ones with equal occurrences, take the last of those.

# Retina, 71 bytes

Lw.+
%($¶$
1%O.
1%L$(.)\1*$.&
)L$^(.+)(¶.+)\2*$
$1 N^$
$.& 0G  Try it online! Link includes test cases. Takes input as a string of digits. Explanation: Lw.+  Get all substrings of the input. %( )  Loop over each substring. $
¶$  Duplicate the substring. 1%O.  Sort the duplicate into order. 1%L$(.)\1*
$.&  Get the run lengths. L$^(.+)(¶.+)\2*1


If the run lengths are equal, then keep the substring, otherwise keep nothing.

N^$$.&


Sort all of the remaining substrings in descending order of length.

0G


Keep only the longest remaining substring.

# Python 2, 140 132 bytes

-8 bytes thanks to @hyper-neutrino for space saving and replacing def with lambda!

I was using python3 to code until I found that it works for Python2 too, not too much, just an iterative solution.

lambda n:max([r for r in [n[i:a]for a in range(len(n)+1)for i in range(len(n))if a-i>1]if len(set(r.count(s)for s in r))<2],key=len)


Try it online!

• You only use l twice, so it's better to make this a lambda and just put len(n) in twice. Also, you have two extra spaces. tio.run/##XY3BDsIgEER/… May 13, 2021 at 5:14

# Charcoal, 40 bytes

ＦＥθ✂θκＦＥι…ι⊕λＦ⁼⌊Ｅκ№κλ⌈Ｅκ№κλ⊞υκΦυ⁼Ｌι⌈ＥυＬλ


Try it online! Link is to verbose version of code. Takes input as a string of digits and outputs all maximal length substrings with the given condition. Explanation:

ＦＥθ✂θκ


Loop over all nontrivial suffixes of the input.

ＦＥι…ι⊕λ


Loop over all nontrivial prefixes of the suffix.

Ｆ⁼⌊Ｅκ№κλ⌈Ｅκ№κλ


Take the frequencies of the elements and check whether they are all the same.

⊞υκ


Record all substrings that satisfy the condition.

Φυ⁼Ｌι⌈ＥυＬλ


Output the longest such substrings.

# Ruby, 69 bytes

->r,*w{r,*w=w<<r[0..-2]<<r[1..-1]while r.map{|x|r.count x}.uniq;r}


Try it online!

# yuno (abandoned), 7 bytes

ッシュフェドゥッキッカ；テ


xxd using Jelly's codepage:

00000000: 87a0 9a6d 6bfe 0b                        ⁷ɦȤmk“¿


Disclaimer: some language features were added after this challenge. However, they weren't really made to be tailored to this challenge, all of these are things I'd planned previously. If I really wanted to, I could've reasonably made built-ins much more suited ot this challenge, but I have those on my wishlist right now as they're a lot more specific.

ッシュフェドゥッキッカ；テ   Full Program
ッシュ　　　　　　　　　　   All sublists, in increasing order of length then position
フェ　　　　　　；　   Filter-lambda; keep elements that:
ドゥ　　　　　　   (duplicate top of stack)
ッキ　　　　   special count; if counting occurrences of a list that is not found, but any of its elements are, vectorize (recurses)
ッカ　　   all-equal?
テ   last element

• So, it is a code page which render a single byte to multiple katakana?
– tsh
May 13, 2021 at 5:36
• @tsh yes, that's how it works. i will admit it's a bit weird and maybe wasn't the best idea :P May 13, 2021 at 15:47

# Python 3.8, 98 bytes

Another not-very-successful python3 attempt

f=lambda l,i=0:(a:=l[i%(L:=len(l)):][:L-i//L])*(i%L<=i//L)*(len({*map(a.count,a)})<2)or f(l,i+1)


a less condensed version

def f(l, i=0):
L = len(l)
a = l[i%L:][:L-i//L]
return a * (i%L<=i//L) * (len({*map(a.count,a)})<2) or f(l,i+1)
`