Блог пользователя bokuto_alright

Difficult Amazon OA problem
Автор bokuto_alright, история, 5 месяцев назад, По-английски

Saw this on LC discussion and have no idea how to approach. https://leetcode.com/discuss/interview-question/5365200/Amazon-OA

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 месяцев назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

in case if all characters in the password are distinct. The number of distinct passwords formed by reversing any substring would be represented as all substring of size>=2 ie.. ((n*(n+1)/2) -1) - n +1 where ((n*(n+1)/2) -1) accounts for the substring of atleast one character, n is substring of exactly one character and 1 for the case of no reversal.

In general, the formula becomes ((n*(n+1)/2) -1)- P +1 where P is the number of palindromic substrings of size >=1. as reversing it would create the same substring.

UPD : It's incorrect.

→ Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Same problem as this? https://stackoverflow.com/questions/78108438/number-of-unique-strings-that-can-be-formed-by-reversing-one-substring-of-a-stri

→ Ответить
  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is. Thank you

    → Ответить
    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It seems logically incorrect to me.

      For example, the answer for "abca" would be 6 {abca, baca, acba, abac, cbaa, aacb}, but the answer from the mentioned solution would be 5, which is incorrect.

      → Ответить
      • »
        »
        »
        »
        5 месяцев назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        No, it is correct actually. I coded up the solution and the answer for abca is 6 only Code for reference ->

        My Code
        → Ответить
        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Sorry for the mistake. I misread last time. It is totally correct.

          "A substring would cause overcounting if its endpoints have the same character, as reversing it would create the same substring as reversing the substring of length 2 less formed by removing the leftmost and rightmost character."

          This is quite logical and must be correct.

          → Ответить