This is a little challenge with the goal of identifying repeated pattern "blocks" in a string, and outputting them with their frequency of occurence from left to right.

A friend asked me this question and I realized it wasn't as simple as tossing what you've seen into a hash table and popping them off if previously seen.

Example Input and Output



The idea:

T T | B B | P P P | BP BP BP | B B B B | PB PB PB | B


2T, 2B, 3P, 3BP, 4B, 3PB, B

However any output format that shows the number of repetitions, and respective repeated substrings, are allowed.

Is it possible to do this with reasonable time complexity?

I'm curious as to the standard, legible approach to this kind of question, but as this is code golf - shortest code wins!


  • 1
    \$\begingroup\$ Welcome to PPCG!. This seems a good challenge though you need to specify what is the winning criteria. \$\endgroup\$ – Luis felipe De jesus Munoz Jan 4 '19 at 20:24
  • 1
    \$\begingroup\$ @R.Gosman Welcome to PPCG, where people abuse code to the fullest extent to golf it! Seriously though, please don't consider PPCG as an example of good practices. :P Also, is this challenge restricted to Python? \$\endgroup\$ – Erik the Outgolfer Jan 4 '19 at 20:36
  • 4
    \$\begingroup\$ What if several outputs are possible? For instance, what is the expected result for "ABABCABCBC"? \$\endgroup\$ – Arnauld Jan 4 '19 at 20:44
  • 7
    \$\begingroup\$ ...also what about AAABBBAAABBB is it [A3, B3, A3, B3], [AAABBB2], or [[A3, B3]2]? \$\endgroup\$ – Jonathan Allan Jan 4 '19 at 20:52
  • 1
    \$\begingroup\$ I've voted to close as unclear, but I think this is a good challenge! As you're new here, you probably haven't heard of The Sandbox, but it's pretty useful for refining challenges to fit our expectations, and for preventing the comments section from blowing up. \$\endgroup\$ – Giuseppe Jan 4 '19 at 21:21