Secret.Codes's blog

Is it possible to get the length of biggest substring which is palindrome on a string on O(n)??
By Secret.Codes, history, 7 years ago, In English

Is it possible to get the length of biggest substring which is palindrome on a string on O(n)??

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

There are two ways that I know of to solve this.

→ Reply
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Hashes + 2 pointers

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

    Can you explain how this will work?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +44 Vote: I do not like it

      We can use the idea similar to 2 pointers instead of binary search.

      1. Fix the "center" of palindrome
      2. Check all subsrtings that have greater length, that previous answer does.
      3. Update answer if it is possible

      It will be O(N)

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      We will visit all centers, it's O(n). In every position we will try to update answer. All updates will work summary O(ans) = O(n), so algorithm's complexity is O(n).

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    I only know O(n log n) solution with hashes using binary search, how can it be done in O(n)?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      If we change

      for (int len = 0; len <= max_possible; i++)

      in naive O(N^2) solution to

      for (int len = ans; len <= max_possible; i++)

      it will improove complexity to O(N)

      → Reply