Longest Repeating Subsequence of a Single Digit

Question

Challenge:

Given a positive integer, output the longest single-digit subsequence that occurs at least twice, AND has boundaries of another digit (or the start/end of the integer).

An example:

Input: 7888885466662716666
The longest subsequence of a single digit would be 88888 (7[88888]5466662716666) with a length of 5. However, this subsequence only occurs once in the integer.
Instead, the result for input 7888885466662716666 should be 6666 (78888854[6666]271[6666]), since it occurs (at least) twice.

Challenge rules:

• Length of the subsequences takes priority over the amount of times it occurs. (I.e. with input 8888858888866656665666, we output 88888 ([88888]5[88888]66656665666; length 5, occurs twice), and not 666 (88888588888[666]5[666]5[666]; length 3, occurs thrice).
• If the length of multiple subsequences are equal, we output the one with the largest occurrence-count. I.e. with input 3331113331119111, we output 111 (333[111]333[111]9[111]; length 3, occurs thrice), and not 333 ([333]111[333]1119111; length 3 as well, but occurs twice)
• If the occurrence-count and length of multiple subsequences are equal, you can output either of them, or all (in any order). I.e. with input 777333777333, the possible outputs are: 777; 333; [777, 333]; or [333, 777].
• The subsequence must have boundaries of other digits (or the start/end of the integer). I.e. with input 122222233433 the result is 33 (1222222[33]4[33]; length 2, occurs twice) and not 222 (1[222][222]33433, length 3, occurs twice with both invalid).
  • This applies to all numbers that are counted towards the occurrence-counter. I.e. with input 811774177781382 the result is 8 ([8]117741777[8]13[8]2; length 1, occurs thrice) and not 77 (811[77]41[77]781382 / 811[77]417[77]81382; length 2, occurs twice with one invalid) nor 1 (8[1][1]774[1]7778[1]382; length 1, occurs four times with two invalid).
• You can assume the input won't contain any digits 0 (it will match [1-9]+). (This is to avoid having to deal with test cases like 10002000 that should output 000, where most languages would output 0 by default.)
• You can assume the input will always contain at least one valid output.
• I/O are both flexible. Can be a list/array/stream of digits/bytes/characters or as string instead of a single integer.

General rules:

• This is code-golf, so shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code.
• Also, adding an explanation for your answer is highly recommended.

Test cases:

Input: 7888885466662716666 / [7,8,8,8,8,8,5,4,6,6,6,6,2,7,1,6,6,6,6]
Output: 6666 / [6,6,6,6]
Input: 3331113331119111 / [3,3,3,1,1,1,3,3,3,1,1,1,9,1,1,1]
Output: 111 / [1,1,1]
Input: 777333777333 / [7,7,7,3,3,3,7,7,7,3,3,3]
Possible outputs: 777; 333; [777,333]; [333;777] / [7,7,7]; [3,3,3]; [[7,7,7],[3,3,3]]; [[3,3,3],[7,7,7]]
Input: 122222233433 / [1,2,2,2,2,2,2,3,3,4,3,3]
Output: 33 / [3,3]
Input: 811774177781382 / [8,1,1,7,7,4,1,7,7,7,8,1,3,8,2] 
Output: 8 / [8]
Input: 555153333551 / [5,5,5,1,5,3,3,3,3,5,5,1] 
Output: 1 / [1]
Input: 12321 / [1,2,3,2,1]
Possible outputs: 1; 2; [1,2]; [2,1] / [1]; [2]; [[1],[2]]; [[2],[1]]
Input: 944949949494999494 / [9,4,4,9,4,9,9,4,9,4,9,4,9,9,9,4,9,4]
Output: 4 / [4]
Input: 8888858888866656665666 / [8,8,8,8,8,5,8,8,8,8,8,6,6,6,5,6,6,6,5,6,6,6]
Output: 88888 / [8,8,8,8,8]
Input: 1112221112221111 / [1,1,1,2,2,2,1,1,1,2,2,2,1,1,1,1]
Output: 111; 222; [111,222]; [222,111] / [1,1,1]; [2,2,2]; [[1,1,1],[2,2,2]]; [[2,2,2],[1,1,1]]
Input: 911133111339339339339339 / [9,1,1,1,3,3,1,1,1,3,3,9,3,3,9,3,3,9,3,3,9,3,3,9]
Output: 111 / [1,1,1]

• Mr. Xcoder: Suggested test case: 8888858888866656665666. If I interpreted the challenge correctly, both the Brachylog and 05AB1E solutions fail.
• Kevin Cruijssen: @Mr.Xcoder Added, thanks.
• Mr. Xcoder: @Arnauld Hmm, it would be one of the winners anyway in my opinion because it occurs as many times as 222 when bounded by other integers. I guess we just shouldn't count the occurrence that is a substring of 1111. Better wait for the OP though, indeed.
• Kevin Cruijssen: @Arnauld For 1112221112221111 these are the subsequences and their counts: 1111 (1), 111 (2), 222 (2). Since we only outputs sequences occurring at least twice, the output can be one of: 111, 222, [111,222], [222,111]. (See the fourth rule for some more information.) Basically 1111 will only ever count as 1111, and not as 1 and 111 or 11 and 11. I'll add your test case, but the output is either or both of 111 and 222.

Answer 1

Jelly, 12 bytes

Œgœ-Q$LÐṀÆṃ'

Try it online!

Previous version – 14 bytes

ŒgŒQ¬TịƲLÐṀÆṃ'

Try it online!

How it works?

Œgœ-Q$LÐṀÆṃ' – Full program. Receives a list of digits as input.
Œg – Group equal adjacent values.
 œ-Q$ – Multiset difference with itself deduplicate.
 LÐṀ – Keep those that are maximal by length.
 Æṃ' – Mode. Returns the most common element(s).
-------------------------------------------------------------------------
ŒgŒQ¬TịƲLÐṀÆṃ' – Full program. Receives a list of digits as input.
Œg – Group equal adjacent values.
 ŒQ – Distinct sieve. Replace the first occurrences of each value by 1.
 and the rest by 0. [1,2,3,2,3,2,5]ŒQ -> [1,1,1,0,0,0,1] 
 ¬T – Negate and find the truthy indices.
 ịƲ – Then index in the initial list of groups.
 – This discards the groups that only occur once.
 LÐṀ – Find all those which are maximal by length.
 Æṃ' – And take the mode.

Answer 2

05AB1E, 14 bytes

γÐ1ドル›ÏD€gZQÏ.M

Try it online!

Explanation

γ # group consecutive equal elements
 Т # count the occurrence of each group among the list of groups
 1›Ï # keep only groups with a count greater than 1
 D€gZQÏ # keep only those with a length equal to the greatest length
 .M # get the most common item

• Emigna: @Riley: Unfortunately that would get the first element which is not necessarily the most common one.
• Riley: Oops.. I missed that bullet.
• Kevin Cruijssen: 1› can be ≠ for -1 byte. (Also, D€gZQÏ could alternatively be é.¡g}θ for the same byte-count these days. I think .¡ wasn't available yet at the time.)

Answer 3

Retina, 56 bytes

L`(.)1円*
O`
L$m`^(.+)(¶1円)+$
$#2;1ドル
N`
.+;
N$`
$.&
-1G`

Try it online! Link includes test cases. Explanation:

L`(.)1円*

List all the maximally repeated digit subsequences.

O`

Sort the list into order.

L$m`^(.+)(¶1円)+$
$#2;1ドル

List all the multiple subsequences with their "count".

N`

Sort in ascending order of count.

.+;

Delete the counts.

N$`
$.&

Sort in ascending order of length. (Where lengths are equal, the previous order due to count is preserved.)

-1G`

Keep the last i.e. longest value.

Answer 4

JavaScript (ES6), (削除) 79 (削除ここまで) (削除) 73 (削除ここまで) 68 bytes

Takes input as a string. Returns an integer.

s=>[...s,r=q=0].map(o=d=>q=s^d?o[!o[q]|r[q.length]?q:r=q]=s=d:q+d)|r

Try it online!

Commented

s => // s = input string, also used as the current digit
 [ ...s, // split s into a list of digit characters
 r = // r is the final result
 q = // q is the current digit sequence
 0 // append a final dummy entry to force the processing of the last
 ] // sequence
 .map(o = // o is an object used to keep track of encountered sequences
 d => // for each digit d in the array defined above:
 q = // update q:
 s ^ d ? // if d is not equal to the current digit:
 o[ // this statement will ultimately update o[q]
 !o[q] | // if q has not been previously seen
 r[q.length] ? // or the best result is longer than q:
 q // leave r unchanged
 : // else:
 r = q // set r to q
 ] = s = d // reset q to d, set the current digit to d
 // and mark q as encountered by setting o[q]
 : // else:
 q + d // append d to q
 ) | r // end of map(); return r, coerced to an integer

• Kevin Cruijssen: Maybe I'm saying something incorrect here, but since ...s converts the input to a list of digit characters, isn't it shorter to just take the input as a list of digit characters to begin with, instead of a string? I've allowed flexible I/O. (But I'm assuming it interferes with another part of your code?)
• Arnauld: @KevinCruijssen The problem is that I need an extra iteration to process the last sequence. So I'd need to do [...s,0] even if s already is a list.

Answer 5

R, 102 bytes

function(i)rep(names(sort(-(x=(x=table(rle(i)))[rowSums(x>1)>0,,drop=F])[m<-max(rownames(x)),])[1]),m)

Try it online!

Since there wasn't an R answer yet, I decided to give it a try, and well... it wasn't easy. I don't really know whether it is a good approach, but here it goes.

Inputs and outputs vectors of characters.

• ngm: Close to 100 bytes is pretty good for R with this challenge.

Answer 6

Perl 6, (削除) 58 (削除ここまで) 56 bytes

*.comb(/(.)0ドル*/).Bag.max({.value>1,+.key.comb,.{*}}).key

Try it online!

Answer 7

Python 2, (削除) 123 (削除ここまで) 120 bytes

import re
def f(s):r=re.findall(r'(\d)(1円*)',s);c=r.count;print max((len(a+b)*(c((a,b))>1),c((a,b)),a+b)for a,b in r)[2]

Try it online!

Answer 8

Powershell, 101 byte

($args|sls '(.)1円*'-a|%{$_.Matches}|group|?{$_.Count-1}|sort @{e={$_.Name.Length,$_.Count}})[-1].Name

Explanied test script:

$f = {
(
 $args| # for each argument (stings)
 sls '(.)1円*'-a| # searches all
 %{$_.Matches}| # regex matches
 group| # group it (Note: Count of each group > 0 by design)
 ?{$_.Count-1}| # passthru groups with Count not equal 1
 sort @{ # sort all groups by 2 values
 e={$_.Name.Length,$_.Count}
 }
)[-1].Name # returns name of last group (group with max values)
}
@(
 ,('7888885466662716666', '6666')
 ,('3331113331119111', '111')
 ,('777333777333', '777','333')
 ,('122222233433', '33')
 ,('811774177781382', '8')
 ,('555153333551','1')
 ,('12321', '1','2')
 ,('944949949494999494','4')
 ,('8888858888866656665666','88888')
 ,('1112221112221111','111','222')
) | % {
 $s,$e = $_
 $r = &$f $s
 "$($r-in$e): $r"
}

Output:

True: 6666
True: 111
True: 777
True: 33
True: 8
True: 1
True: 1
True: 4
True: 88888
True: 111

Answer 9

Python 2, (削除) 114 (削除ここまで) 113 bytes

-1 byte thanks to TFeld.

p='';r=[];C=r.count
for c in input():r+=['']*(c!=p);r[-1]+=c;p=c
print max((len(w),C(w),w)for w in r if~-C(w))[2]

Try it online!

Answer 10

Haskell, 72 bytes

import Data.Lists
g!x|y<-countElem x g=(y>1,1<$x,y)
(argmax=<<(!)).group

How it works

(argmax=<<(!)).group -- expands to: f i = argmax (group i !) (group i)
 group -- split the input list into subsequences of equal digits
 -- e.g. "1112211" -> ["111","22","11"]
 -- find the element of this list where the function !
 -- returns the maximum value. First parameter to !
 -- is the grouped input list, second parameter the
 -- the element to look at 
g!x|
 y<-countElem x g -- let y be the number of occurrences of x in g
 = ( , , ) -- return a triple of
 y>1 -- a boolean y>1 (remember: True > False) 
 1<$x -- length of x (to be exact: all elements in x
 -- replaced by 1. This sorts the same way as the
 -- length of x)
 y -- y
 -- a triples sorts lexicographical

• ბიმო: Do you not need to use Haskell + lists as language because Data.Lists is not part of base?
• nimi: @BWO: don't know. I've always used a plain "Haskell", even when I imported an exotic library (e.g. Gloss for graphical output or Matrix). I use "Haskell + something" if I don't want to include the byte count for the imports. I think we had this topic on meta, but I cannot find it anymore. If I remember correctly, we had no general definition of "standard library". What should be the reference for Haskell? The Haskell Report, GHC's base, Haskell Plattform, something else?
• ბიმო: IMO it should be as with C/JavaScript/.. that (if it matters) we need to use Haskell (GHC) or Haskell (Hugs) etc. because the implementation specifies a language on PPCG. So for a GHC answer that would include base and for all the other ones I wouldn't know :D
• Kevin Cruijssen: Do you perhaps have a TIO link so it can be tested? Or is the Data.Lists library not available on TIO or another online Haskell compiler?
• nimi: @KevinCruijssen: yes Data.Lists is missing on TIO. You can test it with this version.

Answer 11

R, 85 bytes

function(x,R=rle(x),a=ave(R$v,R,FUN=length))rep(R$v[o<-order(a<2,-R$l,-a)[1]],R$l[o])

Try it online!

• Input : a vector of separated integer digits e.g. c(1,8,8...)

• Output : a vector of separated integer digits

Unrolled code with explanation :

function(x){ # x is a vector of digits : e.g. c(1,1,8,8,1,1)
R = rle(x) # Get the sequences of consecutive repeating digits
 # doing run length encoding on x, i.e. : R is a list
 # with the digits (R$values) and the number of their
 # consecutive occurrencies (R$lengths)
 # N.B. you can use R$v for R$values and R$l for R$lenghts
a=ave(R$v,R,FUN=length) # Group R$v by R$l AND R$v, count the occurrencies 
 # for each group and "unroll" the value of each 
 # group to the original R$v length.
 # Here basically we count the occurrencies of the same 
 # sequence.
o<-order(a<2,-R$l,-a)[1] # Get the indexes used to order by a < 2 then by -R$l and
 # finally by -a; store the first index in "o".
 # Here basically we use order to select the first sequence 
 # repeated at least twice, in case of ties the sequence 
 # with the greatest length and in case of ties the most 
 # repeated sequence.
rep(R$v[o],R$v[o]) # Using the index "o", we reconstruct the sequence repeating
 # R$l[o] times R$v[o]
}

---

Alternative version accepting vector of integer or character digits :

R, 88 bytes

function(x,R=rle(x),a=ave(R$v,R,FUN=length))rep(R$v[o<-tail(order(a>1,R$l,a),1)],R$l[o])

Try it online!

• Input : a vector of separated characters or digits e.g. c("1","8","8"...) or c(1,8,8...)

• Output : a vector of separated characters if the input was a vector of characters, a vector of digits if the input was a vector of digits

• JayCe: Can you add an explanation? I don't understand how it's working.
• digEmAll: @JayCe: done! (I've added details that you well know, just for non-R users ;) )
• JayCe: ty! It makes sense now.

Answer 12

Red, (削除) 256 (削除ここまで) 250 bytes

func[s][p: func[b][sort parse b[collect[any keep[copy a skip thru any a]]]]first
last sort/compare collect[foreach d p p s[if 1 < k: length? to-block d[keep/only
reduce[form unique d k]]]]func[x y][(reduce[length? x/1 x/2])< reduce[length? y/1 y/2]]]

Try it online!

Really, realy long solution this time... (sigh)

Takes the input as a string.

Explanation:

f: func [ s ] [
 p: func [ b ] [ ; groups and sorts the adjacent repeating items
 sort parse b [ 
 collect [ 
 any keep[
 copy a skip thru any a ; gather any item, optionally followed by itself 
 ]
 ]
 ]
 ]
 t: copy []
 foreach d p p s [ ; p p s transforms the input string into a block of sorted blocks of repeating digits
 if 1 < k: length? to-block d [ ; filters only the blocks that occur more than once
 insert/only t reduce [ form unique d k ] ; stores the digits and the number of occurences
 ; "8888858888866656665666" -> [["5" 3] ["666" 3] ["88888" 2]]
 ]
 ]
 first last sort/compare t func [ x y ] ; takes the first element (the digits) of the last block of the sorted block of items
 [ (reduce [ length? x/1 x/2 ]) < reduce [ length? y/1 y/2 ] ] ; direct comparison of the blocks
]

Answer 13

Java (JDK 10), 213 bytes

s->{int l=99,X[][]=new int[10][l],d,D=0,m=0,M=0;for(var x:s.split("(?<=(.))(?!\1円)"))X[x.charAt(0)-48][x.length()]++;for(;M<1&&l-->1;)for(d=0;d++<9;)if((m=X[d][l])>1&m>M){M=m;D=d;}for(;l-->0;)System.out.print(D);}

Try it online!

Explanation (outdated)

s->{ // Lambda for Consumer<String>
 int l=99, // Length of token, max is 99.
 X[][]=new int[10][l], // Array containing the occurrences per token
 d, // digit value
 D=0, // digit holder for best sequence candidate
 m=0, // holder of the current candidate
 M=0; // best candidate for the current length of token.
 for(var x:s.split("(?<=(.))(?!\1円)")) // Tokenize the string into digit-repeating sequences
 X[x.charAt(0)-48][x.length()]++; // Add one occurrence for the token
 for(;M<1&&l-->1;) // While no value has been found and for each length, descending. Do not decrease length if a value has been found.
 for(d=0;d++<9;) // for each digit
 if((m=X[d][l])>1&m>M){ // if the current occurrence count is at least 2 and that count is the current greatest for the length
 M=m;D=d; // mark it as the current best
 } //
 for(;l-->0;)System.out.print(D); // Output the best-fitting subsequence.
} // 

Credits

• -9 bytes and bug spotting thanks to Kevin Cruijssen

• Kevin Cruijssen: I'm afraid there is a small flaw in your j*o>M check. If I understand correctly it takes the max length * occurrence-count. But for a test case like 1113311133933933933933 for example, the 111 would be (3 * 2 = 6), and the 33 would be (2 * 6 = 12). So it outputs 33 having the highest occurrence, instead of 111 being the longest occurring at least twice. Also, var r="";for(;O-->0;)r+=D;return r; can be golfed to for(;O-->0;)System.out.print(D); in Java 10, or even shorter in Java 11: return(D+"").repeat(O);.
• Olivier Grégoire: @KevinCruijssen I think I fixed it.
• Kevin Cruijssen: That indeed looks better, and nice way of golfing bytes at the same time. You just forgot to update your explanation. And you can golf 1 more byte changing int X[][]=new int[10][99],d,l=99, to int l=99,X[][]=new int[10][l],d,.
• Olivier Grégoire: @KevinCruijssen Thanks! I also golfed one more byte by writing d++<9 instead of ++d<10. Sorry for the rest: I'm rather tired today =_=

Answer 14

Ruby, (削除) 68 (削除ここまで) 67 bytes

->a{(b=a.chunk &:+@).max_by{|x|[(c=b.count x)<2?0:x[1].size,c]}[1]}

Try it online!

Inputs and outputs arrays of chars.

The approach is pretty straightforward: we identify the runs of consecutive digits (chunk using unary + as identity function) and take the maximum - first by the size of the run (reset to zero if its occurrence count is < 2), then by the count itself.

Answer 15

Wolfram Language (Mathematica), 67 bytes

#&@@@MaximalBy[Select[Tally@Split@#,Last@#>1&],{Length@#,#2}&@@#&]&

Pure function. Takes a list of digits as input and returns a list of subsequences (in no particular order) as output. Not sure if the "must appear at least twice" clause can be handled more cleanly. Try it online!

• Kevin Cruijssen: Could you perhaps add a TIO link for it?
• LegionMammal978: If you really insist...

Answer 16

PCRE, 152 bytes

(\d)(?<!(?=1円)..)(?=(1円*)(?!1円).*(?!1円).1円2円(?!1円))(?!(?:(?=2円((3円?+)(\d)(5円*)))){1,592}?(?=2円3円.*(?!5円).5円6円(?!5円))(?:1円(?=1円*4円5円(7円?+5円)))*+(?!1円))2円

See it in action on: https://regex101.com/r/0U0dEp/1 (just look at the first match in each test case)

This is just for fun, since regex isn't a real programming language in and of itself, and the solution is limited :P

Because a zero-width group such as (?:)+ only matches once and doesn't repeat indefinitely, and because PCRE internally makes copies of groups quantified with limits, I've had to use a magic number in there ("{1,592}"), which means we can only look up to 592 contiguous sets of digits ahead to find a competing set that could be longer than the one currently under inspection. More info on this concept here.

Answer 17

Vyxal o, 68 bits^v2 , 8.5 bytes

Ġ:UÞ⊍(LO∆M

Try it Online!

groups by identical adjacent digits, finds the duplicated elements, then takes the most common of the longest runs.

Answer 18

Perl 5, 88 bytes

my($m,%s);++$i%2*$s{$_}++&&($n=$s{$_}/9+length)>$m&&($a=$_,$m=$n)for pop=~/((.)2円*)/g;$a

Try it online!

Slightly ungolfed, with tests:

sub f {
 my($m,%s);
 my($i,$n,$a); #not needed in golfed version
 ++$i % 2 * $s{$_}++
 && ($n=$s{$_}/9+length) > $m
 && ($a=$_, $m=$n)
 for pop=~/((.)2円*)/g; #i.e. 7888885466662716666 => 7 88888 5 4 6666 2 7 1 6666
 $a
}
for(map[/\d+/g],split/\n/,join"",<DATA>){ #tests
 my($i,@e)=@$_;
 printf "%-6s input %-24s expected %-10s got %s\n",
 (grep f($i) eq $_, @e) ? "Ok" : "Not ok", $i, join('|',@e), f($i);
}
__DATA__
Input: 7888885466662716666 Output: 6666
Input: 3331113331119111 Output: 111
Input: 777333777333 Output: 777|333
Input: 122222233433 Output: 33
Input: 811774177781382 Output: 8
Input: 555153333551 Output: 1
Input: 12321 Output: 1|2
Input: 944949949494999494 Output: 4
Input: 8888858888866656665666 Output: 88888
Input: 1112221112221111 Output: 111|222

Answer 19

Japt -h, 12 bytes

Input & output are strings.

ò¦ ñÊf@ÓZè¶X

Try it

Answer 20

Husk, (削除) 13 (削除ここまで) 6 bytes

►LṠ-ug

Try it online!

Edit

Turned out, this task could be solved with a very short piece of code.

Explanation

It has taken a while to figure out the correct solution. It boils down to those essential steps:

1. Removal of the items appearing one time only. Here, I was able to improve from these 9-byte-monsters ΣtġLÖLgOg or Σfo>1LgOg (filtering out the list elements) to the more elegant Ṡ-ug (subtraction of every unique element). See also the Jelly answer below.
2. Get the most frequent element from the elements of the maximal length.

Commented:

 g -- group adjacent numbers into sublists
 u -- get unique groups / subsequences
 Ṡ- -- remove unique subsequences from the whole list: 
 -- | this will allow to get rid of the subsequences appearing only once
►L -- take the most common item from the elements of the maximal length.

Old version:

 g -- group adjacent numbers into sublists
 u -- get unique groups / subsequences
 Ṡ- -- remove unique subsequences from the whole list: 
 -- | this will allow to get rid of the subsequences appearing only once
 ÖL -- sort by length
 ġL -- group subsequences by length
 → -- keep the longest subsequence(s)
 ►Lg -- take the most common item 
u -- make unique