bokuto_alright's blog

Difficult Amazon OA problem
By bokuto_alright, history, 5 months ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is. Thank you

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

        My Code
        → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply