Find max sequence length

Question

Assume we have a string, and we want to find the maximum repeated sequence of every letter.

For example, given the sample input:

"acbaabbbaaaaacc"

Output for the sample input can be:

a=5
c=2
b=3

Rules:

• Your code can be function or a program - for you to choose
• Input can be by stdin, file or function parameter
• The output should contain only characters that appear in the input
• Input max length is 1024
• The output order does not matter, but it has to be printed in the form [char]=[maximum repeated sequence][delimiter]
• The string can contain any character

The competition ends on Thursday 3rd at 23:59 UTC.

Answer 1

8086 machine code, 82 80

Contents of the x.com file:

B7 3D 89 DF B1 80 F3 AA 0D 0A 24 B4 01 CD 21 42
38 D8 74 F7 38 17 77 02 88 17 88 C3 31 D2 3C 0D
75 E9 BF 21 3D B1 5E 31 C0 F3 AE E3 EE 4F BB 04
01 8A 05 D4 0A 86 E0 0D 30 30 89 47 02 3C 30 77
04 88 67 03 43 89 3F 89 DA B4 09 CD 21 47 EB D7

It only supports repetitions of up to 99 characters.

Source code (served as input for the debug.com assembler), with comments!

a
    mov bh, 3d         ; storage of 128 bytes at address 3d00
    mov di, bx
    mov cl, 80
    rep stosb          ; zero the array
    db 0d 0a 24
; 10b
    mov ah, 1
    int 21             ; input a char
    inc dx             ; calculate the run length
    cmp al, bl         ; is it a repeated character?
    je  10b
    cmp [bx], dl       ; is the new run length greater than previous?
    ja  11a
    mov [bx], dl       ; store the new run length
; 11a
    mov bl, al         ; remember current repeating character
    xor dx, dx         ; initialize run length to 0
    cmp al, d          ; end of input?
    jne 10b            ; no - repeat
    mov di, 3d21       ; start printing run lengths with char 21
    mov cl, 5e         ; num of iterations = num of printable characters
; 127
    xor ax, ax
    repe scasb         ; look for a nonzero run length
    jcxz 11b           ; no nonzero length - exit
    dec di
    mov bx, 104        ; address of output string
    mov al, [di]       ; read the run length
    aam                ; convert to decimal
    xchg al, ah
    or  ax, 3030
    mov [bx+2], ax
    cmp al, 30         ; was it less than 10?
    ja  145
    mov [bx+3], ah     ; output only one digit
    inc bx             ; adjust for shorter string
; 145
    mov [bx], di       ; store "x=" into output string
    mov dx, bx         ; print it
    mov ah, 9
    int 21
    inc di
    jmp 127            ; repeat
; 150

rcx 50
n my.com
w
q

Here are some golfing techniques used here that I think were fun:

• array's address is 3d00, where 3d is the ascii-code for =. This way, the address for array's entry for character x is 3d78. When interpreted as a 2-character string, it's x=.
• Output buffer is at address 104; it overwrites initialization code that is no longer needed. End-of-line sequence 0D 0A 24 is executed as harmless code.
• The aam instruction here doesn't provide any golfing, though it could...
• Writing the number twice, first assuming it's greater than 10, and then correcting if it's smaller.
• Exit instruction is at an obscure address 11b, which contains the needed machine code C3 by luck.

Answer 2

CJam, 27 26 25 bytes

l:S_&{'=L{2$+_S\#)}g,(N}/

Try it online.

Example

$ cjam maxseq.cjam <<< "acbaabbbaaaaacc"
a=5
c=2
b=3

How it works

l:S       " Read one line from STDIN and store the result in “S”.                   ";
_&        " Intersect the string with itself to remove duplicate characters.        ";
{         " For each unique character “C” in “S”:                                   ";
  '=L     " Push '=' and ''.                                                        ";
  {       "                                                                         ";
    2$+_  " Append “C” and duplicate.                                               ";
    S\#)  " Get the index of the modified string in “S” and increment it.           ";
  }g      " If the result is positive, there is a match; repeat the loop.           ";
  ,       " Retrieve the length of the string.                                      ";
  (       " Decrement to obtain the highest value that did result in a match.       ";
  N       " Push a linefeed.                                                        ";
}/        "                                                                         ";

Answer 3

J - 52 bytes

Well, a simple approach again.

f=:([,'=',m=:":@<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1~~.

Explanation:

f=:([,'=',m=:":@<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1~~.
                                                 ~~. Create a set of the input and apply it as the left argument to the following.
   ([,'=',m=:":@<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1    The function that does the work
                                             "0 1    Apply every element from the left argument (letters) with the whole right argument (text).
                                  @.(+./@E.)         Check if the left string is in right string.
                       (]m~[,{.@[)                   If yes, add one letter to the left string and recurse.
             ":@<:@#@[                               If not, return (length of the left string - 1), stringified.
    [,'=',                                           Append it to the letter + '='

Example:

   f 'acbaabbbaaaaacc'
a=5
c=2
b=3
   f 'aaaabaa'
a=4
b=1

If free-form output is allowed (as in many other answers), I have a 45 bytes version too. These boxes represent a list of boxes (yes, they're printed like that, although SE's line-height breaks them).

   f=:([;m=:<:@#@[`(]m~[,{.@[)@.(+./@E.))"0 1~~.
   f 'acbaabbbaaaaacc'
┌─┬─┐
│a│5│
├─┼─┤
│c│2│
├─┼─┤
│b│3│
└─┴─┘
   f 'aaaabaabba'
┌─┬─┐
│a│4│
├─┼─┤
│b│2│
└─┴─┘

Answer 4

Ruby, 72

(a=$*[0]).chars.uniq.map{|b|puts [b,a.scan(/#{b}+/).map(&:size).max]*?=}

This takes input from command line arguments and outputs to stdout.

Answer 5

GolfScript, 26 bytes

:s.&{61{2$=}s%1,/$-1=,n+}%

Try it online.

Explanation:

• :s saves the input string in the variable s for later use.
• .& extracts the unique characters in the input, which the rest of the code in the { }% loop then iterates over.
• 61 pushes the number 61 (ASCII code for an equals sign) on top of the current character on the stack, to act as an output delimiter.
• {2$=}s% takes the string s and replaces its characters with a 1 if they equal the current character being iterated over, or 0 if they don't. (It also leaves the current character on the stack for output.)
• 1,/ takes this string of ones and zeros, and splits it at zeros.
• $ sorts the resulting substrings, -1= extracts the last substring (which, since they all consist of repetitions of the same character, is the longest), and , returns the length of this substring.
• n+ stringifies the length and appends a newline to it.

Ps. If the equals signs in the output are optional, the 61 can be omitted (and the 2$ replaced by 1$), for a total length of 24 bytes:

:s.&{{1$=}s%1,/$-1=,n+}%

Answer 6

CoffeeScript, 109 bytes

I like regex.

f=(s)->a={};a[t[0]]=t.length for t in s.match(/((.)\2*)(?!.*\1)/g).reverse();(k+'='+v for k,v of a).join '\n'

Here is the compiled JavaScript you can try in your browser's console

f = function(s) {
  var a, t, _i, _len, _ref;
  a = {};
  _ref = s.match(/((.)\2*)(?!.*\1)/g).reverse();
  for (_i = 0, _len = _ref.length; _i < _len; _i++) {
    t = _ref[_i];
    a[t[0]] = t.length;
  }
  return a;
};

Then you can call

f("acbaabbbaaaaacc")

to get

c=2
a=5
b=3

Answer 7

Python 3, 69 bytes

s=input()
for c in set(s):
 i=0
 while-~i*c in s:i+=1
 print(c,'=',i)

Try it online!

Even golfed Python can be very readable. I think this code is fully idiomatic except for the -~i for i+1 and the single-letter variables. Thanks to pxeger for saving 1 byte.

Example runs:

>>> helloworld
e = 1
d = 1
h = 1
l = 2
o = 1
r = 1
w = 1
>>> acbaabbbaaaaacc
a = 5
c = 2
b = 3

Answer 8

Pyth, 24 25 26 (or 29)

=ZwFY{Z=bkW'bZ~bY)p(Yltb

Test can be done here: link

Outputs in the format:

('a', 5)
('c', 2)
('b', 3)

Explanation:

=Zw              Store one line of stdin in Z
FY{Z             For Y in set(Z):
=bk              b=''
W'bZ             while b in Z:
~bY              b+=Y
)                end while
p(Yltb           print (Y, len(b)-1)

Python:

k=""
Z=copy(input())
for Y in set(Z):
 b=copy(k)
 while (b in Z):
  b+=Y
 print(_tuple(Y,len(tail(b))))

For proper (a=5) output, use:

=ZwFY{Z=bkW'bZ~bY)p++Y"="`ltb

29 characters

Answer 9

C, 126 125 119 bytes

l,n,c[256];main(p){while(~(p=getchar()))n*=p==l,c[l=p]=c[p]>++n?c[p]:n;for(l=256;--l;)c[l]&&printf("%c=%d\n",l,c[l]);}

Running:

$ gcc seq.c 2>& /dev/null
$ echo -n 'acbaabbbaaaaacc' | ./a.out
c=2
b=3
a=5

Answer 10

Mathematica, 74 72 69

Print[#[[1,1]],"=",Max[Tr/@(#^0)]]&/@Split@Characters@#~GatherBy~Max&

% @ "acbaabbbaaaaacc"

a=5
c=2
b=3

Not very good but strings are not Mathematica's best area. Getting better though. :-)

Answer 11

C# (LinQPad)

146

This is tsavino's answer but shorter. Here, I used Distinct() instead of GroupBy(c=>c). Also the curly braces from the foreach-loop are left out:

void v(string i){foreach(var c in i.Distinct())Console.WriteLine(c+"="+(from Match m in Regex.Matches(i,"["+c+"]+")select m.Value.Length).Max());}

---

136

I tried using a lambda expression instead of the normal query syntax but since I needed a Cast<Match> first, the code became 1 character longer... Anyhow, since it can be executed in LinQPad, you can use Dump() instead of Console.WriteLine():

void v(string i){foreach(var c in i.Distinct())(c+"="+(from Match m in Regex.Matches(i,"["+c+"]+")select m.Value.Length).Max()).Dump();}

---

Further study of the code got me thinking about the Max(). This function also accepts a Func. This way I could skip the Select part when using the lambda epxression:

void v(string i){foreach(var c in i.Distinct())(c+"="+Regex.Matches(i,"["+c+"]+").Cast<Match>().Max(m=>m.Value.Length)).Dump();}

Thus, final result:

128

Update:

Thanks to the tip from Dan Puzey, I was able to save another 6 characters:

void v(string i){i.Distinct().Select(c=>c+"="+Regex.Matches(i,"["+c+"]+").Cast<Match>().Max(m=>m‌​.Value.Length)).Dump();}

Length:

122

Answer 12

Ruby, 58

h={}
gets.scan(/(.)\1*/){h[$1]=[h[$1]||0,$&.size].max}
p h

Takes input from STDIN, outputs it to STDOUT in the form {"a"=>5, "c"=>2, "b"=>3}

Answer 13

C# in LINQPad - 159 Bytes

Well, at least I beat T-SQL ;P Won't beat anyone else, but I thought I'd share it anyway.

void v(string i){foreach(var c in i.GroupBy(c=>c)){Console.WriteLine(c.Key+"="+(from Match m in Regex.Matches(i,"["+c.Key+"]+")select m.Value.Length).Max());}}

Usage:

v("acbaabbbaaaaacc");

Suggestions are always welcome!

Answer 14

Powershell 80 77 72

$x=$args;[char[]]"$x"|sort -u|%{"$_="+($x-split"[^$_]"|sort)[-1].length}

You need to run it on console...

Answer 15

Perl - 65 71 76 characters

My first code golf!

For each answer, copy to golf.pl and run as:

echo acbaabbbaaaaacc | perl golf.pl

My shortest solution prints each character as many times as it appears, since that is not prohibited by the rules.

$_=$i=<>;for(/./g){$l=length((sort$i=~/$_*/g)[-1]);print"$_=$l
"}

My next-shortest solution (85 90 characters) only prints each character once:

<>=~s/((.)\2*)(?{$l=length$1;$h{$2}=$l if$l>$h{$2}})//rg;print"$_=$h{$_}
"for keys %h

Answer 16

F# - 106

let f s=
 let m=ref(Map.ofList[for c in 'a'..'z'->c,0])
 String.iter(fun c->m:=(!m).Add(c,(!m).[c]+1))s;m

In FSI, calling

f "acbaabbbaaaaacc"

gives

val it : Map<char,int> ref =
  {contents =
    map
      [('a', 8); ('b', 4); ('c', 3); ('d', 0); ('e', 0); ('f', 0); ('g', 0);
       ('h', 0); ('i', 0); ...];}

However, to print it without the extra information, call it like this:

f "acbaabbbaaaaacc" |> (!) |> Map.filter (fun _ n -> n > 0)

which gives

val it : Map<char,int> = map [('a', 8); ('b', 4); ('c', 3)]

Answer 17

Javascript, 116 bytes

y=x=prompt();while(y)r=RegExp(y[0]+'+','g'),alert(y[0]+'='+x.match(r).sort().reverse()[0].length),y=y.replace(r,'')

Sample output:

lollolllollollllollolllooollo
l=4
o=3

acbaabbbaaaaacc
a=5
c=2
b=3

helloworld
h=1
e=1
l=2
o=1
w=1
r=1
d=1 

Answer 18

T-SQL (2012) 189 171

Edit: removed ORDER BY because rules allow any output order.

Takes input from a CHAR variable, @a, and uses a recursive CTE to create a row for each character in the string and figures out sequential occurrences.

After that, it's a simple SELECT and GROUP BY with consideration for the order of the output.

Try it out on SQL Fiddle.

WITH x AS(
    SELECT @a i,''c,''d,0r,1n
    UNION ALL 
    SELECT i,SUBSTRING(i,n,1),c,IIF(d=c,r+1,1),n+1
    FROM x
    WHERE n<LEN(i)+2
)
SELECT d+'='+LTRIM(MAX(r))
FROM x
WHERE n>2
GROUP BY d

Assigning the variable:

DECLARE @a CHAR(99) = 'acbaabbbaaaaacc';

Sample output:

a=5
c=2
b=3

Answer 19

Haskell - 113 120 bytes

import Data.List
main=interact$show.map(\s@(c:_)->(c,length s)).sort.nubBy(\(a:_)(b:_)->a==b).reverse.sort.group

Tested with

$ printf "acbaabbbaaaaacc" | ./sl
[('a',5),('b',3),('c',2)]

Answer 20

JavaScript [83 bytes]

prompt().match(/(.)\1*/g).sort().reduce(function(a,b){return a[b[0]]=b.length,a},{})

^{Run this code in the browser console.}

For input "acbaabbbaaaaacc" the console should output "Object {a: 5, b: 3, c: 2}".

Answer 21

JavaScript - 91

for(i=0,s=(t=prompt()).match(/(.)\1*/g);c=s[i++];)t.match(c+c[0])||alert(c[0]+'='+c.length)

EDIT: My first solution obeys the rules, but it prints several times single char occurrences like abab => a=1,b=1,a=1,b=1 so I came out with this (101 chars), for those not satisfied with my first one:

for(i=0,s=(t=prompt()).match(/((.)\2*)(?!.*\1)/g);c=s[i++];)t.match(c+c[0])||alert(c[0]+'='+c.length)

Answer 22

Husk, 18 bytes

mȯJ'=§eo;←osL►Lk←g

Try it online!

11 bytes if we ignore the exact input format and display as a list of pairs instead.

Answer 23

Husk, 16 bytes

mS:(:'=s▲`mg¹#)U

Try it online!

Explanation:

m              U    # for each of the unique elements of the input
 S:                 # prepend the element to
   (:'=       )     # '=' prepended to
        ▲           # the maximum of
             #      # the number of times it occurs in 
         `mg¹       # each group of identical items in the input,
       s            # converted into a string

I saw that Razetime had answered this in Husk, so I had to have a go too...

Answer 24

Jelly, 12 bytes

ŒriƇṀj”=ʋⱮQY

Try it online!

-2 bytes thanks to Unrelated String!

8 bytes to output as a list of pairs

How it works

ŒriƇṀj”=ʋⱮQY - Main link. Takes a string S on the left
        ʋ    - Group the previous 4 links into a dyad f(S, C):
Œr           -   Run-length encode S
   Ƈ         -   For each sublist in rle(S), keep it if:
  i          -     It contains C
    Ṁ        -   Maximum
                 As all elements are in the form [C, n] for integers n,
                 Python considers the maximum as the greatest n
     j”=     -   Join with "="; Yields [C, "=", n]
          Q  - Get the unique characters of S
         Ɱ   - For each unique character C in S, yield f(C, S)
           Y - Join by newlines and output

Answer 25

Bash / GNU core utils (40)

fold -1|uniq -c|sort -k2 -k1r|uniq -f1

Try it online!

Output when input is "acbaabbbaaaaacc":

      5 a
      3 b
      2 c

Explanation:

• fold -1 adds a newline after each character
• uniq -c counts the number of consecutive identical lines
• sort -k2 -k1r sorts the result so as the maximum count for each character comes first
• uniq -f1 keeps only the first line for each character

Answer 26

Julia, 85

f(s)=(l=0;n=1;a=Dict();[c==l?n+=1:(n>get(a,l,1)&&(a[l]=n);n=1;l=c) for c in s*" "];a)
julia> f("acbaabbbaaaaacc")
{'a'=>5,'c'=>2,'b'=>3}

Answer 27

Python3 - 111, 126, 115 114 111 bytes

Executable code that will read 1 line (only use lowercase letters a-z)

d={}.fromkeys(map(chr,range(97,123)),0)
for c in input():d[c]+=1
[print("%s=%d"%(p,d[p]))for p in d if d[p]>0]

Edit: Excluded unnecessary output on request from @Therare

The output looks nice

~/codegolf $ python3 maxseq.py 
helloworld
l=3
o=2
h=1
e=1
d=1
w=1
r=1

Answer 28

JavaScript - 141 137 125

I don't like regex :)

function g(a){i=o=[],a=a.split('');for(s=1;i<a.length;){l=a[i++];if(b=l==a[i])s++;if(!b|!i){o[l]=o[l]>s?o[l]:s;s=1}}return o}

Run

console.log(g("acbaabbbaaaaacc"));

outputs

[ c: 2, a: 5, b: 3 ]

Answer 29

Javascript, 109 104 100 98 bytes

function c(s){q=l={};s.split('').map(function(k){q[k]=Math.max(n=k==l?n+1:1,q[l=k]|0)});return q}

Example usage:

console.log(c("aaaaaddfffabbbbdb"))

outputs:

{ a: 5, d: 2, f: 3, b: 4 }

Answer 30

PHP, 104 102 96

<?php function _($s){while($n=$s[$i++]){$a[$n]=max($a[$n],$n!=$s[$i-2]?$v=1:++$v);}print_r($a);}

usage

_('asdaaaadddscc');

printed

Array ( [a] => 4 [s] => 1 [d] => 3 [c] => 2 )