5
\$\begingroup\$

Introduction

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

Input:

"TTBBPPPBPBPBPBBBBPBPBPBB"

The idea:

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

Output:

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!

Cheers!

\$\endgroup\$

closed as unclear what you're asking by fəˈnɛtɪk, Giuseppe, Riker, Xcali, Erik the Outgolfer Jan 4 at 21:52

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 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 at 20:36
  • 4
    \$\begingroup\$ What if several outputs are possible? For instance, what is the expected result for "ABABCABCBC"? \$\endgroup\$ – Arnauld Jan 4 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 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 at 21:21