Saturday, July 4, 2015

LeetCode OJ - Longest Palindromic Substring

Problem:

Please find the problem here.

Solution:

In order to solve this problem - I learnt the Manacher's algorithm. Unlike usual, the presentation in geeksforgeeks is awful. This one is much better. The code below is basically an implementation of the idea in the better one without actually constructing the string.

First of all, we insert a '#' sign at the beginning, the end, and between every characters of the input. By doing this, we make sure the longest palindrome of the resulting string is always of odd length.

ababa -> #a#b#a#b#a# 

Of course, we assume '#' is a character that never appears in the original string.

Next, we insert a '^' sign at the beginning of the string and a '$' sign at the end of the string. This is to make our code even easier to write, without having to worry about the boundaries.

Next we come to our key idea. We do not know where is the center of the longest palindrome. So we try each one of them. For each character, we compute the longest palindrome substring with that character as center (this is possible because we know all palindromes have odd lengths). To find the longest palindrome substring, just check if s[c + k] = s[c - k] and try to increase k as much as possible, that results in a quadratic algorithm.

It can be speed up using the property of palindrome. It is easier to discuss the speed up with some simple notations. Denote H[c] be the half length of a palindrome. Remember all palindrome is of odd length? H[c[ is a ceiling of the half. For example

S   # a # a # a # a #
idx 0 1 2 3 4 5 6 7 8
H   1 2 3 4 ?

H[3] = 4 because the palindrome is '#a#a#a#' with length 7. It can also be thought of as the number of characters extending to one side, as in the both characters.

Now here is the key observation. How do we compute H[4] quickly? Let's look at what we have:

S   # a # a # a # a # // H[3] = 4 implies red parts are mirrors
S   # a # a # a # a # // H[2] = 3 implies green parts are mirrors
idx 0 1 2 3 4 5 6 7 8
H   1 2 3 4 ?

Now use the first mirror to flip the greens around? We can imply this!

S   # a # a # a # a # // inferred the blue parts are mirror
idx 0 1 2 3 4 5 6 7 8
H   1 2 3 4 ?

So now we can simply claim H[4] is at least 3, but of course we know this is not the end of it. In this case we have to extend our search, but starting from 3!

Sometimes mirroring force us to trim the string, let see this example.

S   # a # b # a # b # a # b # 
idx 0 1 2 3 4 5 6 7 8 9 A B C
H   1 2 1 4 1 5 1 6 1 ?

Given H[7] = 6 and H[5] = 5, what can we say about H[9]? Using the same color code, we can see that

S   # a # b # a # b # a # b # // H[7] = 6 implies red 
S   # a # b # a # b # a # b # // H[5] = 5 implies green
idx 0 1 2 3 4 5 6 7 8 9 A B C
H   1 2 1 4 1 5 1 6 1 ?

Note that part of the green string is outside of the red range, so we have no choice but to ignore them when flipping:

S   # a # b # a # b # a # b # // H[7] = 6 implies red 
S   # a # b # a # b # a # b # // H[5] = 5 implies green
S   # a # b # a # b # a # b # // reduced green parts 
S   # a # b # a # b # a # b # // inferred blue
idx 0 1 2 3 4 5 6 7 8 9 A B C
H   1 2 1 4 1 5 1 6 1 ?

Now we can happily claim the value of H[9] = 4.

Without further ado, here is the code for the algorithm:

#include "stdafx.h"

// https://leetcode.com/problems/longest-palindromic-substring/

#include "LEET_LONGEST_PALINDROMIC_SUBSTRING.h"

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <string>

using namespace std;

namespace _LEET_LONGEST_PALINDROMIC_SUBSTRING
{
    class Solution
    {
    public:
        string longestPalindrome(string s)
        {
            int conceptual_length = s.length() * 2 + 3;
            vector<int> palindrome_half_lengths;
            palindrome_half_lengths.resize(conceptual_length - 1); // We do not need to palindrome_half_lengths of the $ character

            // Initialization - the ^ character match nothing, so palindrome_half_lengths[0] = 1
            palindrome_half_lengths[0] = 1;
            int current_center = 0;
            int current_palindrome_inclusive_ends = 0;
            for (int i = 1; i < conceptual_length - 1; i++) // avoid moving beyond $.
            {
                // Step 1: Infer the certainly mirroring half length at position i
                int certainly_mirroring_half_length = 1;
                if (current_palindrome_inclusive_ends > i)
                {
                    int inclusive_remaining_length = current_palindrome_inclusive_ends - i + 1;
                    int mirror_position = current_center - (i - current_center);
                    int mirror_palindrome_half_length = palindrome_half_lengths[mirror_position];
                    if (inclusive_remaining_length < mirror_palindrome_half_length)
                    {
                        certainly_mirroring_half_length = inclusive_remaining_length;
                    }
                    else
                    {
                        certainly_mirroring_half_length = mirror_palindrome_half_length;
                    }
                }
                else
                {
                    certainly_mirroring_half_length = 1;
                }

                // Step 2: Expand 
                while (get_conceptual_character(s, i - certainly_mirroring_half_length + 1) == get_conceptual_character(s, i + certainly_mirroring_half_length - 1))
                {
                    certainly_mirroring_half_length++;
                }
                certainly_mirroring_half_length--;

                palindrome_half_lengths[i] = certainly_mirroring_half_length;

                // Step 3: Update boundaries
                if (i + certainly_mirroring_half_length > current_palindrome_inclusive_ends)
                {
                    current_center = i;
                    current_palindrome_inclusive_ends = i + certainly_mirroring_half_length;
                }
            }
            /*
            for (int i = 1; i < conceptual_length - 1; i++)
            {
                cout << i ;
                cout << "\t";
                print_conceptual_character(s, i);
                cout << " ";
                cout << palindrome_half_lengths[i];
                cout << endl;
            }
            */
            int max_index = -1;
            int max_value = -1;

            for (int i = 1; i < conceptual_length - 1; i++)
            {
                if (palindrome_half_lengths[i] > max_value)
                {
                    max_value = palindrome_half_lengths[i];
                    max_index = i;
                }
            }
            // suppose conceptual index 10 is the palindrome, and max_value is 5.
            // which means [6, 7, 8, 9, 10] == [10, 11, 12, 13, 14] 
            int s_index = max_index - max_value + 1;
            int e_index = max_index + max_value - 1;
            s_index++;
            e_index--;
            return s.substr(s_index / 2 - 1, (e_index - s_index) / 2 + 1);
        }
    private:
        pair<char, int> get_conceptual_character(string& s, int position)
        {
            if (position == 0)
            {
                return pair<char, int>(0, 1);
            }
            else if (position % 2 == 1)
            {
                return pair<char, int>(0, 2);
            }
            else if (position == (s.length() + 1) * 2)
            {
                return pair<char ,int>(0, 3);
            }
            else
            {
                return pair<char, int>(s[position / 2 - 1], 0);
            }
        }

    };
};

using namespace _LEET_LONGEST_PALINDROMIC_SUBSTRING;

int LEET_LONGEST_PALINDROMIC_SUBSTRING()
{
    Solution solution;
    string s = "ababc";
    cout << s << endl;
    cout << solution.longestPalindrome(s) << endl;
    return 0;
}

No comments :

Post a Comment