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!

Improve this question
\$\endgroup\$
10
  • 1
    \$\begingroup\$ Welcome to PPCG!. This seems a good challenge though you need to specify what is the winning criteria. \$\endgroup\$ Commented Jan 4, 2019 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\$ Commented Jan 4, 2019 at 20:36
  • 4
    \$\begingroup\$ What if several outputs are possible? For instance, what is the expected result for "ABABCABCBC"? \$\endgroup\$ Commented Jan 4, 2019 at 20:44
  • 7
    \$\begingroup\$ ...also what about AAABBBAAABBB is it [A3, B3, A3, B3], [AAABBB2], or [[A3, B3]2]? \$\endgroup\$ Commented Jan 4, 2019 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\$ Commented Jan 4, 2019 at 21:21

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.