The most common substring

Question

The purpose of this task is to write a program or function to find the most common substring within a given string, of the specified length.

Inputs

1. A string, s, of any length and characters that are valid as inputs for your language.
2. A number, n, indicating the length of substring to find. Guaranteed to be equal to or less than the length of the string.

Output

The most common (case-sensitive) substring of s of length n. In the case of a tie, any of the options may be output.

Win Criteria

This is code-golf, so lowest bytes wins; usual exceptions etc. apply.

Examples

Hello, World!, 1 > l (appears 3 times)
Hello! Cheerio!, 2 > o! (appears twice)
The Cat sat on the mat, 2 > at (appears three times)
The Cat sat on the mat, 3 > at or he (both with trailing spaces. Both appear twice - note case-sensitivity so The and the are different substrings)
Mississippi, 4 > issi (appears twice, note that the two occurrences overlap each other)

Some more examples, all using the same input string^*

Bb:maj/2
F:maj/5
Bb:maj/2
G:9/3
Bb:maj7
F:maj/3
G:min7
C:sus4(b7,9)
C:sus4(b7,9)
C:sus4(b7,9)
F:maj
F:maj

(note the trailing newline)

1 > \r\n(appears 12 times, counting \r\n as a single character - my choice, your code may differ on this - otherwise either \r or \n appear the same number of times). : also appears 12 times
2 > :m (appears 8 times)
3 > :ma or maj (appears 7 times)
4 > :maj (appears 7 times)
5 > F:maj or \r\nF:ma or :maj/ (appears 4 times)
14 > \r\nC:sus4(b7,9)\r\n (appears 3 times)

_{(* input is taken from How predictable is popular music?. The result of this task might be used, for example, to find the most efficient way to apply a substitution in order to compress the string)}

Answer 1

Python 3.8, 75 68 97 63 bytes

lambda s,n:max(l:=[s[j:j+n]for j in range(len(s))],key=l.count)

You can try it online! Increased byte count because, as @xnor kindly pointed out, Python's str.count doesn't count overlapping substrings... But then @xnor's reformulation of what I was doing allowed to slice a third of the bytes!

How:

l:=[s[j:j+n]for j in range(len(s))]

This creates a list of all the substrings in s of size n, plus the suffixes of size n-1, n-2, ..., 1. Then we find the max on that list, with the numerical value being used to sort given by

l.count

That means that if a and b are from l, a > b if a shows up more times in l than b. This means the shorter suffixes are never the result of the max because they only show up once, and even if the correct-sized substrings only show up once, they are first in l so they come out instead of the short suffixes. This allows me to save some bytes in the range used, given that I don't have to prevent i+n from being larger than len(s).

# Python, 83 64 bytes

lambda s,n:max((s[i:i+n]for i in range(len(s)-n+1)),key=s.count)

Thanks to @mypetlion I saved a LOT of bytes :D

You can try it online with my very own incredible test case!

Answer 2

05AB1E, 5 bytes

ŒIù.M

Try it online or verify the smaller test cases or verify the larger test case (which is a bit slow).

Explanation:

Π     # Push all substrings of the (implicit) input-string
 Iù    # Only keep substrings of a length equal to the second input-integer
   .M  # Only keep the most frequent item of the remaining substrings
       # (after which it is output implicitly as result)

Answer 3

Brachylog, 8 bytes

s₎ᶠọtᵒth

Try it online!

Explanation

  ᶠ        Find all…
s          …substrings of <1st element of input>…
 ₎         …of length <2nd element of input>
   ọ       Get the list of each substring with its number of occurrence
    tᵒ     Order by the number of occurrence
      t    Take the last one
       h   Output the substring itself

Answer 4

JavaScript (ES6),  85 83  80 bytes

Takes input as (string)(length).

s=>n=>[...s].map(o=m=(x,i)=>(o[k=s.substr(i,n)]=-~o[k])<m|!k[n-1]?0:m=o[O=k])&&O

Try it online!

Answer 5

Java 10, 212 211 196 195 146 143 bytes

s->n->{String r="",t;for(int m=0,c,j,i=s.length();i-->n;)for(c=0,j=-1;(j=s.indexOf(t=s.substring(i-n,i),j+1))>=0;)if(++c>m){m=c;r=t;}return r;}

-15 bytes by outputting the substrings with their count, which is allowed.
-1 byte thanks to @ceilingcat.
-52 bytes thanks to @OlivierGrégoire.

Try it online.

Explanation:

s->n->{         // Method with String and Integer parameters and String return-type
  String r="",  //  Result-String, starting empty
         t;     //  Temp-String
  for(int m=0,  //  Largest count, starting at 0
          c,    //  Temp count integer
          j,    //  Temp index integer
          i     //  Index-integer `i`
      =s.length();i-->n;)
                //  Loop `i` in the range (input-length, n]:
    for(c=0,    //   Reset the temp-count to 0
        j=-1;   //   And the temp-index integer to -1
        (j=s.indexOf(t=s.substring(i-n,i)
                //   Set String `t` to a substring of the input-String in the range [i-n,i)
           j+1))//   Set the temp-index `j` to the index of String `t` in the input-String,
                //   only looking at the trailing portion after index `j+1`
        >=0;)   //   And continue looping as long as long as that substring is found
      if(++c>m){//    If the temp-count + 1 is larger than the current largest count:
        m=c;    //     Set this current largest count to this temp-count + 1
        r=t;}   //     And the result-String to this temp-String
  return r;}    //  After the nested loops, return the result-String

Answer 6

Perl 6, 49 46 bytes

-3 bytes thanks to SirBogman

{$^n;bag($^a~~m:ov/.**{$n}/X~$).max(*{*}).key}

Try it online!

Explanation

{                                            }  # Anonymous block
 $^n;  # Declare argument
         $^a~~m   /       /  # Regex match input string
               :ov           # Also return overlapping matches
                   .**{$n}   # Match n-character strings
                           X~$   # Stringify matches
     bag(                     )  # Convert to Bag (multiset)
                               .max(*{*})  # Find Pair string=>count with max value
                                         .key  # Get key (string)

Answer 7

PHP, 133 126 bytes

for(;$k<=strlen($i=$argv[1])-$j=$argv[2];)$s[]=substr($i,$k++,$j);$c=array_count_values($s);asort($c);echo array_key_last($c);

Try it online!

Annoyingly asort() and end() can't be chained into one expression.

-7 bytes thanks to @manatwork

Answer 8

JavaScript (Node.js), 92 bytes

s=>n=>s.map(F=t=>([F[w=(w+t).slice(-n)]=-~F[w],w]),w="").sort(([a],[b])=>a-b)[s.length-1][1]

Try it online!

Takes s as a list of characters in (s)(n) syntax.

Answer 9

C# (Visual C# Interactive Compiler), 97, 96, 92 bytes

s=>n=>s.Skip(n-1).Select((_,i)=>s.Substring(i,n)).GroupBy(x=>x).OrderBy(g=>g.Count()).Last()

Try it online!

Explanation:

s.Skip(n-1).Select((_,i)=>s.Substring(i,n)) //select every substring of size n
    .GroupBy(x=>x)                          //group by value
        .OrderBy(g=>g.Count())              //order by increasing recurrence
            .Last()                         //return the last one

Answer 10

Charcoal, 28 bytes

ＮθＦ⊕⁻Ｌηθ⊞υ✂ηι⁺θιＵＭυ⟦№υιι⟧⊟⌈υ

Try it online! Link is to verbose version of code. Outputs the lexicographically largest substring with the highest count. Explanation:

Ｎθ

Input the desired substring length.

Ｆ⊕⁻Ｌηθ⊞υ✂ηι⁺θι

Extract all substrings of that length and push them to a list.

ＵＭυ⟦№υιι⟧

Replace each substring with a tuple of its count and the substring..

⊟⌈υ

Print the substring with the highest count.

Answer 11

Japt -g, 8 bytes

ãV ü ñÊÌ

Try it

Answer 12

Wolfram Language (Mathematica), 30 bytes

#&@@Commonest[##~Partition~1]&

Takes an array of characters, returns an array of characters.

Try it online!

Wolfram Language (Mathematica), 36 bytes

#&@@Commonest[##~StringPartition~1]&

Takes a string, returns a string.

Try it online!

Answer 13

Zsh, 89 bytes

local -A m
repeat $#1 ((++m[${1:$[i++]:$2}]))
for k v (${(kv)m})((v>M))&&r=$k&&M=$v
<<<$r

Try it online!

local -A m                    # associative array, "local" is shorter than "typeset"
repeat $#1 {                  # looping for the length of the string will cause the
                              # program to use shorter, invalid strings as
                              # the bash-style slice gets cut short
    ((++m[${1:$[i++]:$2}]))   # increment the map at the key with substring
}                             # starting at $[i++] with length $2
for k v (${(kv)m}) {          # loop over the associative array's keys/values
    ((v>M)) && r=$k && M=$v   # find the max value M, save the key as r.
}                             # looping forward ensures we avoid our invalid subtrings
<<<$r                         # print $r

Answer 14

C++ (clang), ^{201 \$\cdots\$ 151} 150 bytes

#import<map>
using S=std::string;S f(S s,int n){std::map<S,int>m;S t,r;for(int i=0,x=0;i<=s.size()-n;r=x<++m[t=s.substr(i++,n)]?x=m[t],t:r);return r;}

Try it online!

Ungolfed

#include<map>
#include<string>
std::string f(const std::string& s,int n) {
    std::map<std::string,int> m;
    for(int i=0;i<=s.size()-n;++i) {
        m[s.substr(i,n)]++;
    }
    int x=0;
    std::string r;
    for(auto a:m) {
         if(x<a.second) {
             x=a.second;
             r=a.first;
         }
    }
    return r;
}

Answer 15

Excel (Ver. 1911), 60 Bytes

B2 'Input: String
B3 'Input: Sub-string Length
C2 =-COUNTIF(D2#,D2#)
D2 =MID(B2,SEQUENCE(LEN(B2)),B3)
E2 =SORT(C2#:D2)
F2 'Output

Test Sample

Note: Newlines do exist in cells, but default formatting doesn't show them. Also only 10 of the 105 rows are shown to keep the image a decent size.

Answer 16

Jelly, 6 bytes

I have a feeling there may be an elusive 5-byter out there.

ṡċ@Þ`Ṫ

Try it online!

Answer 17

PowerShell, 72 bytes

param($s,$n)(0..($s.Length-$n)|%{$s|% s*g $_ $n}|group|sort C*|% N*)[-1]

Try it online!

Unrolled:

param($s,$n)
(
    0..($s.Length-$n)|%{
        $s|% substring $_ $n
    }|group|sort Count|% Name
)[-1]

Answer 18

Ruby, 58 bytes

->s,n{a=(0..s.size).map{|i|s[i,n]};a.max_by{|e|a.count e}}

Try it online!

Answer 19

Perl 5 -lp, 47 bytes

++$k{$_}>$k{$\}&&($\=$_)for<>=~/(?=(.{$_}))/g}{

Try it online!

Answer 20

Japt -h, 8 bytes

ãV
ñ@è¶X

Try it

Answer 21

Go, 131 bytes

func f(s string,l int)(p string){x,i:=0,0
m:=map[string]int{}
for;i<=len(s)-l;i++{t:=s[i:i+l]
m[t]++
if m[t]>x{x=m[t]
p=t}}
return}

Takes as input a string and an int representing the string and the length of the substring respectively.

Some newlines can be replaced by semicolons if people prefer one-liners.

Try it online!