# Longest Repeating Subsequence of a Single Digit

## 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 , 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.
• 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]

• Suggested test case: 8888858888866656665666. If I interpreted the challenge correctly, both the Brachylog and 05AB1E solutions fail. – Mr. Xcoder Sep 17 '18 at 8:23
• @Mr.Xcoder Added, thanks. – Kevin Cruijssen Sep 17 '18 at 8:27
• @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. – Mr. Xcoder Sep 17 '18 at 8:38
• @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. – Kevin Cruijssen Sep 17 '18 at 8:55

# 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

• @Riley: Unfortunately that would get the first element which is not necessarily the most common one. – Emigna Sep 18 '18 at 18:54
• Oops.. I missed that bullet. – Riley Sep 18 '18 at 18:56

# 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.  # JavaScript (ES6), 7973 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  • 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?) – Kevin Cruijssen Sep 17 '18 at 10:54 • @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. – Arnauld Sep 17 '18 at 10:57 # 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. # 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. • Close to 100 bytes is pretty good for R with this challenge. – ngm Sep 18 '18 at 18:39 # Perl 6, 58 56 bytes *.comb(/(.)$0*/).Bag.max({.value>1,+.key.comb,.{*}}).key


Try it online!

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

# 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  # 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! ## 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? – ბიმო Sep 18 '18 at 22:02 • @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? – nimi Sep 18 '18 at 22:34 • 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 – ბიმო Sep 18 '18 at 23:39 • 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? – Kevin Cruijssen Sep 19 '18 at 10:23 • @KevinCruijssen: yes Data.Lists is missing on TIO. You can test it with this version. – nimi Sep 19 '18 at 16:45 # 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

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

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


# 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

• 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);. – Kevin Cruijssen Sep 18 '18 at 11:48
• @KevinCruijssen I think I fixed it. – Olivier Grégoire Sep 18 '18 at 12:23
• 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,. – Kevin Cruijssen Sep 18 '18 at 12:46
• @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 =_= – Olivier Grégoire Sep 18 '18 at 13:15

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

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

# 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


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

• Could you perhaps add a TIO link for it? – Kevin Cruijssen Sep 18 '18 at 6:22
• If you really insist... – LegionMammal978 Sep 18 '18 at 10:17

# Japt -h, 12 bytes

Input & output are strings.

ò¦ ñÊf@ÓZè¶X


Try it