Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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 have to be printer in the form [char]=[maximum repeated sequence][delimiter]
  • The string can contain any character

Competition ends on Thursday 3rd at 23:59 UTC.

share|improve this question
    
Do we need to write an entire program, or is a function enough? –  ProgramFOX yesterday
    
mmm... Im new here, I think it will be better if you decide - whats more common? –  yossico yesterday
    
You could say that both a function and a program is OK, because a function is shorter in some languages, but a program is shorter in some other languages. –  ProgramFOX yesterday
2  
Does the output have to be exactly as given? Can we say 0 for letters that don't appear? Will every letter up to the highest letter appear at least once? –  xnor yesterday
1  
Please clarify if the output has to be formatted exactly as exemplified in your question. At least 10 of the current 16 answers use a different format, three others present two different versions. –  Dennis yesterday
show 4 more comments

34 Answers

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.
share|improve this answer
add comment

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.                                                        ";
}/        "                                                                         ";
share|improve this answer
add comment

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.

share|improve this answer
    
chars is a bit shorter than split(""). –  Ventero yesterday
    
@Ventero I tried that, but chars gives an enumerator rather than an array. I am in 1.9.3, so is it a 2.0 thing? –  voidpigeon yesterday
    
Yeah, in 2.0 chars returns an array. –  Ventero yesterday
add comment

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│
└─┴─┘
share|improve this answer
add comment

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+}%
share|improve this answer
1  
You can save the swap if you push the 61 first: :s.&{61{2$=}s%1,/$-1=,n+}%. –  Howard yesterday
    
@Howard: Thanks! –  Ilmari Karonen 23 hours ago
add comment

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
share|improve this answer
    
This seems to generate incorrect results for input like aaaabaa. –  Ventero yesterday
    
@Ventero you're right, there are two problems. one is easily fixed, but I need to think about the other. –  m.buettner yesterday
    
@Ventero fixed. –  m.buettner yesterday
add comment

Python 3 (70)

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

Example run:

>>> helloworld
e = 1
d = 1
h = 1
l = 2
o = 1
r = 1
w = 1
share|improve this answer
    
This is an interesting solution –  Cruncher 21 hours ago
    
if you change set(s) to just s I think it still meets the requirements. Nowhere does it say each char must be printed only once. –  Cruncher 21 hours ago
    
@Cruncher I agree the OP doesn't specify each letter once, but the other Python answers seem to assume it, so I'll stick with that to be comparable. Though output formats are still inconsistent. I do wish the OP had responded to the requests to clarify. –  xnor 20 hours ago
add comment

bash + utils 41, or 62

Edit2: Well, losing compatibility can save another 10 bytes by dropping the #!/bin/sh line. This will probably work for most shells, and I believe the current shell will assume a script of the same type. See comments here.

Edit: thanks to Dennis for some improvements.

Save the following to file ssc.sh then $ chmod +x ssc.sh

fold -1|uniq -c|sort -rk2|awk '!a[$2]++'

Description: Replace each character with character and newline, count the number of times consecutive lines appears, sort by the count in reverse order (most-seen first), send to awk which outputs each line that hasn't been seen before based on the character column.

Example:

/codegolf/substring_count$ ./ssc.sh <<< "aabbccbbbbccca"
      3 c
      4 b
      2 a

And, for output as specified in the challenge for a total of 62 bytes, use

fold -1|uniq -c|sort -rk2|awk '!a[$2]++'|awk '{print$2"="$1}'

Which gives:

codegolf/substring_count$ ./ssc2.sh <<< "aabbccbbbbccca"
c=3
b=4
a=2
share|improve this answer
    
fold -1 does the same as your sed command. You don't need printf if you just read from STDIN. –  Dennis yesterday
    
Thanks for the tips. –  tolos yesterday
1  
Even if required, shebangs are usually not included in the byte count, since you could always invoke the script as bash ssc.sh. Your script doesn't use any bashisms; any POSIX compatible shell will be able to execute it. In any case, the proper shebang for a Bash script would be #!/bin/bash, since sh might be a different shell. –  Dennis yesterday
add comment

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

share|improve this answer
    
Seems like you had the exact same idea. Have a +1 for that. –  TheRare yesterday
    
@TheRare yeah, it seems like a very good way to do it. –  isaacg yesterday
    
I can't deny, can I? –  TheRare yesterday
    
Not really related to your algorithm, but the python output is confusing, because k='' is defined elsewhere. –  gggg yesterday
    
Yeah, sorry about that. I'll work on improving it. I'll edit it too. –  isaacg yesterday
add comment

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
share|improve this answer
    
You could replace getchar()>0 by ~getchar() like in this answer –  anatolyg 5 hours ago
    
@anatolyg Is EOF guaranteed to be exactly -1? I thought it was only specifically defined as being <0. –  fluffy 4 hours ago
    
I think -1 is common enough (i.e. Windows and linux) so you can assume it for Code Golf. For production code, less than zero is perfectly OK, but == EOF is more clear. –  anatolyg 4 hours ago
    
@anatolyg Sure, and actually I guess per the spec EOF apparently isn't even guaranteed to be <0 - it could also be, for example, 256. So I'll just save the single byte. :) –  fluffy 4 hours ago
1  
EOF is guaranteed to be negative, and -1 is used even if char is signed; see here –  anatolyg 4 hours ago
show 1 more comment

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)]
share|improve this answer
add comment

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}

share|improve this answer
add comment

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. :-)

share|improve this answer
add comment

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 
share|improve this answer
add comment

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!

share|improve this answer
add comment

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
share|improve this answer
    
I don't think I've seen a SQL solution here before. Interesting. –  Seiyria 21 hours ago
add comment

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)
share|improve this answer
add comment

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)]
share|improve this answer
    
You can use the . (compose) function to avoid creating a lambda where the parameter only appears after the end of a chain of $ connected functions. To do this, simply change all the $s to .s (example: (\i->reverse$sort$group i) turns into reverse.sort.group. –  YawarRaza7349 6 hours ago
    
Thanks, I had not noticed. –  MomemtumMori 1 hour ago
add comment

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}
share|improve this answer
add comment

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
share|improve this answer
    
You really should exclude the unnecessary output. (I think) –  TheRare yesterday
    
"fixed" the output –  Dog eat cat world yesterday
    
You can remove spaces between braces, numbers and keywords, such as for or if. –  TheRare yesterday
2  
I think you've misread the questions. l=2 and o=1 for "helloworld" –  gnibbler yesterday
4  
You're counting total appearances instead of maximum consecutive appearances. –  xnor yesterday
show 2 more comments

Python 3.x, 88 chars:

from re import*;a=input();[(i[0],len(max(i))) for i in(re.findall(l+"+",a)for l in set(a))]

Outputs in a format of:

[('b', 3), ('c', 2), ('a', 5)]
share|improve this answer
    
This doesn't take input, but otherwise looks like a good approach. –  gggg yesterday
    
Also you're missing an import re or __import__('re') for the findall. –  WorldSEnder yesterday
    
fixed, I forgot I was testing it interactively ;) –  jermenkoo yesterday
add comment

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 ]
share|improve this answer
add comment

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 }
share|improve this answer
add comment

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 )
share|improve this answer
add comment

Java 247

import java.util.*;public class a{public static void main(String[]a){Map<Character, Integer> m = new HashMap<>();for(char c:a[0].toCharArray()){Integer v=m.get(c);m.put(c,v==null?1:v+1);}for(char c:m.keySet())System.out.println(c+"="+m.get(c));}}
share|improve this answer
    
Does import java.util.*; work in Java? –  TheRare 22 hours ago
    
yes and i paste old code –  user902383 22 hours ago
    
The OP said it could just be a function/method so you can shorten this to simply the method. –  Rudi Kershaw 19 hours ago
add comment

C 169

Iterates each printable character in ASCII table and counts max from input string.

#define N 128
int c,i,n;
char Y[N],*p;
int main(){gets(Y);
for(c=33;c<127;c++){p=Y;n=0,i=0;while(*p){if(*p==c){i++;}else{n=(i>n)?i:n;i=0;}p++;}
if(n>0) printf("%c=%d\n",c,n);}
}
share|improve this answer
    
Have you tested this? It doesn't look like it produces correct output on a lot of strings , and also doesn't meet the spec which says that input can be up to 1024 long... plus, there's a lot of easy golfing techniques that you've missed. :) –  fluffy 3 hours ago
add comment

JavaScript 116

prompt(x={}).replace(/(.)\1*/g,function(m,l){n=m.length
if(!x[l]||x[l]<n)x[l]=n})
for(k in x)console.log(k+'='+x[k])
share|improve this answer
add comment

Powershell 80

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

You need to run it on console...

share|improve this answer
add comment

R (219, 213, 197, 196, 191 characters)

Golfed version

f=function(x){x=strsplit(x,"")[[1]];y=list(cumsum(c(1,x[-1]!=head(x,-1))));d=data.frame(a=tapply(x,y,`[`,1),n=tapply(x,y,length));d=d[order(-d$n),];d=d[!duplicated(d$a),];paste0(d$a,"=",d$n)}

Ungolfed version

f <- function(x) {
  x <- strsplit(x, "")[[1]]
  y <- list(cumsum(c(1, x[-1] != head(x, -1))))
  d <- data.frame(a = tapply(x, y, `[`, 1),
                  n = tapply(x, y, length))
  d <- d[order(-d$n), ]
  d <- d[!duplicated(d$a), ]
  paste0(d$a, "=", d$n)
}

f("acbaabbbaaaaacc")
f("acbaabbbaaaaaccdee")
share|improve this answer
add comment

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}".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.