Longest Sublist with Equal Occurrences

Question

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 code-golf, 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).

Answer 1

Brachylog, ⁸ 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] [1] [2,3] [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.
         

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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!

Answer 7

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

Answer 8

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!

Answer 9

05AB1E, 9 8 bytes

ŒʒD¢Ë}éθ

Try it online!

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

Answer 10

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[0] 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

Answer 11

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

Answer 12

R, 104 98 96 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

Answer 13

Haskell, 92 bytes

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 challenge¹.

---

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

Answer 14

J, ³⁸ 33 bytes

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

Try it online!

^{-5 thanks to xash!}

Answer 15

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.

Answer 16

Factor, 63 58 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.

Answer 17

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.

Answer 18

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.

Answer 19

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!

Answer 20

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.

Answer 21

Ruby, 69 bytes

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

Try it online!

Answer 22

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

Answer 23

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)