The best achievable space complexity will always be O(n)

  • 0

    You either have to use some extra O(n) space like a stack, or have to use the space originally occupied by the string itself, which is also O(n).
    In the latter method, the string itself is destroyed in the process though.

    I can use crypto hash to mimic O(1) space complexity, but there will always be collisions (even though rarely, and needs careful construction) that can give out incorrect result.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.