Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
Skins
  • Light
  • Cerulean
  • Cosmo
  • Flatly
  • Journal
  • Litera
  • Lumen
  • Lux
  • Materia
  • Minty
  • Morph
  • Pulse
  • Sandstone
  • Simplex
  • Sketchy
  • Spacelab
  • United
  • Yeti
  • Zephyr
  • Dark
  • Cyborg
  • Darkly
  • Quartz
  • Slate
  • Solar
  • Superhero
  • Vapor

  • Default (No Skin)
  • No Skin
Collapse

The New Coffee Room

  1. TNCR
  2. General Discussion
  3. Puzzle time - non repeating string

Puzzle time - non repeating string

Scheduled Pinned Locked Moved General Discussion
6 Posts 2 Posters 53 Views
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • jon-nycJ Online
    jon-nycJ Online
    jon-nyc
    wrote on last edited by
    #1

    Is there a finite string of letters from the Latin alphabet with the property that there is no pair of adjacent identical substrings, but the addition of any letter to either end would create one?

    (Examples: In the string ABCBCA there is a pair of adjacent identical substrings, namely BC followed immediately by another BC. But the string ABCACB has no such pair.)

    "You never know what worse luck your bad luck has saved you from."
    -Cormac McCarthy

    1 Reply Last reply
    • KlausK Offline
      KlausK Offline
      Klaus
      wrote on last edited by
      #2

      Yes.

      1 Reply Last reply
      • KlausK Offline
        KlausK Offline
        Klaus
        wrote on last edited by
        #3

        click to show

        Consider the case of an alphabet with just two letters AB.

        Now consider the string ABA. It doesn't have the property.

        It has four possible extensions:

        AABA, BABA, ABAA, ABAB

        They all have the property.

        Something like that should also work for 26 letters.

        1 Reply Last reply
        • KlausK Offline
          KlausK Offline
          Klaus
          wrote on last edited by Klaus
          #4

          Here's an example that works for a 3 letter alphabet.

          click to show

          ABACABA

          Here's one for 4 letters:

          click to show

          ABACABADABACABA

          I think I understood the construction principle now. I refrain from executing it for 26 letters since the string would have 2^26 - 1 characters.

          1 Reply Last reply
          • KlausK Offline
            KlausK Offline
            Klaus
            wrote on last edited by Klaus
            #5

            Ah, got it now for the general case.

            click to show

            Let L_n be the n-th letter.

            Let S_1 = L_1

            Let S_(n+1) = S_n, L_(n+1), S_n

            Then S_26 is the string with the desired property.

            By the way, there is a well-known programming technique called hash consing with which such data which grows in size exponentially can still be represented in memory with linear space.

            1 Reply Last reply
            • jon-nycJ Online
              jon-nycJ Online
              jon-nyc
              wrote on last edited by
              #6

              That seems right to me.

              "You never know what worse luck your bad luck has saved you from."
              -Cormac McCarthy

              1 Reply Last reply
              Reply
              • Reply as topic
              Log in to reply
              • Oldest to Newest
              • Newest to Oldest
              • Most Votes


              • Login

              • Don't have an account? Register

              • Login or register to search.
              • First post
                Last post
              0
              • Categories
              • Recent
              • Tags
              • Popular
              • Users
              • Groups