HackerRank Build a Palindrome Problem Solution

HackerRank Build a Palindrome Problem Solution

Yashwant Parihar,

In this post, we will solve HackerRank Build a Palindrome Problem Solution.

You have two strings, a and b. Find a string, s, such that:

  • s can be expressed as s = 8a+ st where 8, is a non-empty substring of a and so is a non-empty substring of b.
  • $ is a palindromic string.
    The length of $ is as long as possible.
    For each of the q pairs of strings (a and b) received as input, find and print strings, on a
    new line. If you’re able to form more than one valid string $;, print whichever one comes
    first alphabetically. If there is no valid answer, print -1 instead.
    Input Format
    The first line contains a single integer, q, denoting the number of queries. The subsequent
    lines describe each query over two lines:
  1. The first line contains a single string denoting a.
  2. The second line contains a single string denoting b.

Output Format
For each pair of strings (a and b), find some s; satisfying the conditions above and print it
on a new line. If there is no such string, print -1 instead.

Sample Input

3
bac
bac
abc
def
jdfh
fds

Sample Output

aba
-1
dfhfd

Explanation
We perform the following three queries:

  1. Concatenate s₁ = “a” with s = “ba” to create s = “aba”.
  2. We’re given a = “abc” and sa = “def”; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print -1.
  3. Concatenate s = “dfh” with s¿ = “fd” to create s = “dfhfd”. Note that we chose these particular substrings because the length of string s must be maximal.
HackerRank Build a Palindrome Problem Solution
HackerRank Build a Palindrome Problem Solution

Build a Palindrome C Solution

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>
#define SWAP(_X, _Y, __type)    \
    do{                        \
        __type __tmp = _X;      \
        _X = _Y;                \
        _Y = __tmp;             \
    }while(0)
#define MAX(__X, __Y) ((__X) > (__Y) ? (__X) : (__Y))
#define MIN(__X, __Y) ((__X) < (__Y) ? (__X) : (__Y))
struct interval
{
    int mid;
    int odd;
    int begin;
    int end;
};
int icmp(const void *p1, const void *p2)
{
    const struct interval *i1 = p1;
    const struct interval *i2 = p2;
    if( i1 -> begin < i2 -> begin )
    {
        return -1;
    }
    else if( i1 -> begin > i2 -> begin )
    {
        return 1;
    }
    return 0;
}
int *_find_longest_palindromes(int *radius[2], int len)
{
    int *result;
    struct interval *intervals;
    int num_intervals = 0;
    result = malloc(sizeof(*result) * len);
    for( int i = 0 ; i < len ; ++i )
    {
        result[i] = 1;
    }
    intervals = malloc(sizeof(*intervals) * len * 2);
    for( int j = 0 ; j < 2 ; ++j )
    {
        for( int i = 0 ; i < len ; ++i )
        {
            if( radius[j][i] != 0 )
            {
                intervals[num_intervals].odd = j;
                intervals[num_intervals].mid = i;
                intervals[num_intervals].begin = intervals[num_intervals].mid - radius[j][i];
                intervals[num_intervals].end = intervals[num_intervals].mid - 1;
                ++num_intervals;
            }
        }
    }
    if( num_intervals > 0 )
    {
        int _num_intervals = 1;
        qsort(intervals, num_intervals, sizeof(*intervals), icmp);
        for( int i = 1 ; i < num_intervals ; ++i )
        {
            if( intervals[_num_intervals - 1].end < intervals[i].begin )
            {
                intervals[_num_intervals++] = intervals[i];
            }
            else if( intervals[_num_intervals - 1].end <= intervals[i].end )
            {
                if( intervals[i].begin == intervals[_num_intervals - 1].begin && ( intervals[_num_intervals - 1].end < intervals[i].end || intervals[i].odd ) )
                {
                    intervals[_num_intervals - 1] = intervals[i];
                }
                else
                {
                    intervals[_num_intervals - 1].end = intervals[i].begin - 1;
                    intervals[_num_intervals++] = intervals[i];
                }
            }
        }
        num_intervals = _num_intervals;
    }
    for( int i = 0 ; i < num_intervals ; ++i )
    {
        for( int j = intervals[i].begin ; j <= intervals[i].end ; ++j )
        {
            result[j] = 2 * ( intervals[i].mid - j ) + intervals[i].odd;
        }
    }
    free(intervals);
    return result;
}
int* find_longest_palindromes(const char *s, int len)
{
    int *result, *radius[2];
    radius[0] = malloc(sizeof(int) * len);
    radius[1] = malloc(sizeof(int) * len);
    radius[0][0] = radius[1][0] = 0;
    for( int j = 0 ; j < 2 ; ++j )
    {
        int i = 1, r = 0;
        while( i < len )
        {
            int k = 1;
            if( s[i] != 0x60 )
            {
                for( register int left = i - r - 1, right = i + r + j ; left >= 0 && right < len && s[left] == s[right] ; --left, ++right, ++r );
                radius[j][i] = r;
            }
            else
            {
                radius[j][i] = r = 0;
            }
            while( k < r && radius[j][i - k] != r - k )
            {
                radius[j][i + k] = MIN(radius[j][i - k], r - k);
                ++k;
            }
            r = r > k ? r - k : 0;
            i += k;
        }
    }
    result = _find_longest_palindromes(radius, len);
    free(radius[0]);
    free(radius[1]);
    return result;
}
int * LCP(const char *s, int len, int *sa)
{
    int k = 0;
    int *lcp, *rank;
    lcp = calloc(len, sizeof(*lcp));
    rank = calloc(len, sizeof(*rank));
    for( int i = 0 ; i < len ; ++i )
    {
        rank[sa[i]] = i;
    }
    for( int i = 0 ; i < len ; ++i )
    {
        if( rank[i] == len - 1 )
        {
            k = 0;
        }
        else
        {
            int j = sa[rank[i] + 1];
            while( i + k < len && j + k < len && s[i+k] == s[j+k] )
            {
                k++;
            }
            lcp[rank[i]] = k;
        }
        if( k != 0 )
        {
            --k;
        }
    }
    free(rank);
    return lcp;
}
struct state
{
    int suffix;
    int bucket[2];
};
int * SA(const char *s, int len)
{
    int *p = malloc(sizeof(int) * len);
    int *sa = malloc(sizeof(int) * len);
    struct state *state, *tmp;
    state = malloc(sizeof(*state) * len);
    tmp = malloc(sizeof(*tmp) * len);
    for( int i = 0 ; i < len ; ++i )
    {
        p[i] = s[i] - 0x60 + 1;
    }
    for( int h = 1 ; h < len ; h <<= 1 )
    {
        for( int i = 0 ; i < len ; ++i )
        {
            state[i].suffix = i;
            state[i].bucket[0] = p[i];
            if( i + h < len )
            {
                state[i].bucket[1] = p[i+h];
            }
            else
            {
                state[i].bucket[1] = 0;
            }
        }
        for( int i = 1 ; i >= 0 ; --i )
        {
            for( int div = 1 ; MAX(len, 28) / div > 0 ; div *= 10 )
            {
                int count[10] = {0};
                for( int j = 0 ; j < len ; ++j )
                {
                    ++count[(state[j].bucket[i] / div) % 10];
                }
                for( int j = 1 ; j < 10 ; ++j )
                {
                    count[j] += count[j-1];
                }
                for( int j = len - 1 ; j >= 0 ; --j )
                {
                    register int index = ( state[j].bucket[i] / div ) % 10;
                    tmp[--count[index]] = state[j];
                }
                SWAP(tmp, state, struct state *);
            }
        }
        for( int i = 0, bucket = 0 ; i < len ; ++i )
        {
            if( ( h << 1 ) >= len || i == 0 || state[i-1].bucket[0] != state[i].bucket[0] || state[i-1].bucket[1] != state[i].bucket[1] )
            {
                ++bucket;
            }
            p[state[i].suffix] = bucket;
        }
    }
    free(state);
    free(tmp);
    for( int i = 0 ; i < len ; ++i )
    {
        sa[p[i]-1] = i;
    }
    free(p);
    return sa;
}
char *build_palindrome(const char *a, const char *b)
{
    int alen = strlen(a), blen = strlen(b), *sa, *lcp, *p, *lcp_ab, maxlen = 0, suffix = -1;
    char *result = NULL;
    int slen = alen + blen + 1;
    char *s = malloc(sizeof(char) * ( slen + 1 ));
    memcpy(s, a, alen);
    s[alen] = 0x60;
    for( int i = 0 ; i < blen ; ++i )
    {
        s[alen+1+i] = b[blen-1-i];
    }
    s[slen] = '\0';
    sa = SA(s, slen);
    lcp = LCP(s, slen, sa);
    lcp_ab = calloc(slen, sizeof(*lcp_ab));
    int i = 1;
    while( i < slen - 1 )
    {
        if( lcp[i] && ( ( sa[i] > alen && sa[i+1] < alen ) || ( sa[i] < alen && sa[i+1] > alen ) ) )
        {
            int j, current = lcp[i];
            for( j = i ; j > 0 && ( ( sa[i] > alen ) ? ( sa[j] > alen ) : ( sa[j] < alen ) ) && lcp[j] > 0 ; --j )
            {
                current = MIN(current, lcp[j]);
                lcp_ab[j] = MAX(lcp_ab[j], current);
            }
            current = lcp[i];
            for( j = i + 1 ; j < slen && ( ( sa[i] > alen ) ? ( sa[j] < alen ) : ( sa[j] > alen ) ) && lcp[j-1] > 0 ; ++j )
            {
                lcp_ab[j] = current = MIN(current, lcp[j - 1]);
            }
            i = j - 1;
        }
        else
        {
            ++i;
        }
    }
    p = find_longest_palindromes(s, slen);
    for( int i = 1 ; i < slen ; ++i )
    {
        if(lcp_ab[i])
        {
            int len = 2 * lcp_ab[i];
            if( ( sa[i] < alen && sa[i] + lcp_ab[i] < alen ) || ( sa[i] > alen && sa[i] + lcp_ab[i] < slen ) )
            {
                len += p[sa[i] + lcp_ab[i]];
            }
            if( len > maxlen )
            {
                suffix = i;
                maxlen = len;
            }
        }
    }
    if(maxlen)
    {
        int len = 0;
        result = malloc(sizeof(*result) * ( maxlen + 1 ));
        memcpy(result, s + sa[suffix], lcp_ab[suffix]);
        if( maxlen > lcp_ab[suffix] * 2 )
        {
            memcpy(result + lcp_ab[suffix], s + sa[suffix] + lcp_ab[suffix], maxlen - lcp_ab[suffix] * 2);
        }
        for( int i = 0 ; i < lcp_ab[suffix] ; ++i )
        {
            result[maxlen-lcp_ab[suffix]+i] = s[sa[suffix] + lcp_ab[suffix]-1-i];
        }
        result[maxlen] = '\0';
    }
    free(sa);
    free(lcp);
    free(lcp_ab);
    free(p);
    free(s);
    return result;
}
int main()
{
    int n;
    scanf("%d", &n);
    while( n-- != 0 )
    {
        char *a, *b, *p;
        a = malloc(131072 * sizeof(*a));
        b = malloc(131072 * sizeof(*b));
        scanf("%s", a);
        scanf("%s", b);
        p = build_palindrome(a, b);
        if( p == NULL )
        {
            printf("-1\n");
        }
        else
        {
            printf("%s\n", p);
        }
        free(p);
        free(a);
        free(b);
    }
    return 0;
}

Build a Palindrome C++ Solution


#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <list>
#include <memory>
#include <unordered_map>
#include <functional>

namespace algorithm_lib
{
	class longest_palindromic_substring_t
	{
	public:
		static std::vector<size_t> max_lengths(const std::string& input)
		{
			if (input.empty())
				return std::vector<size_t>();

			auto input_with_boundaries = add_boundaries(input);
			std::vector<size_t> radius(input_with_boundaries.size());
			size_t reference_boundary = 2;
			size_t reference_center = 1;
			radius[0] = 0;
			radius[1] = 1;
			for (size_t k = 2; k < input_with_boundaries.size(); ++k)
			{
				size_t mirror_radius = radius[reference_center * 2 - k];
				if (k + mirror_radius < reference_boundary)
				{
					radius[k] = mirror_radius;
				}
				else
				{
					reference_center = k;
					size_t r = std::max(reference_boundary, k) - k;
					while (reference_center > r &&
						reference_center + r < input_with_boundaries.size() - 1 &&
						input_with_boundaries[reference_center - r - 1] == input_with_boundaries[reference_center + r + 1])
						++r;
					radius[k] = r;
					reference_boundary = k + r;
				}
			}
			reference_boundary = input_with_boundaries.size() - 1;
			std::vector<size_t> output(input.size());
			for (size_t k = input_with_boundaries.size() - 2; k != 0; --k)
			{
				size_t new_boundary = k - radius[k];
				while (reference_boundary > new_boundary)
				{
					reference_boundary -= 2;
					output[reference_boundary / 2] = k - reference_boundary;
				}
			}
			return output;
		}

	private:
		static std::string add_boundaries(const std::string& input)
		{
			std::string output;
			for (auto c : input)
			{
				output.push_back('|');
				output.push_back(c);
			}
			output += '|';
			return output;
		}
	};
}

namespace algorithm_lib
{
	class suffix_tree_t
	{
	private:
		class node_t
		{
		public:
			size_t start;
			std::shared_ptr<size_t> end;
			std::unordered_map<char, std::shared_ptr<node_t>> children;
			node_t(size_t start, std::shared_ptr<size_t> end)
				: start(start), end(end)
			{}
		};

		typedef std::shared_ptr<node_t> nodeptr;

	private:
		nodeptr _root;
		std::string _text;

	public:
		suffix_tree_t(const std::string& text)
			: _text(text)
			, _root(std::make_shared<node_t>(-1, nullptr))
		{
			size_t suffix_count = 0;

			auto end = std::make_shared<size_t>(text.size());

			for (size_t k = 0; k < text.size(); ++k)
			{
				++suffix_count;
				do {
					if (false == create_internal_node(_root, suffix_count - 1, k, end))
						break;
				} while (--suffix_count);
			}
		}

		std::string max_repeated_substring()
		{
			std::string max_path;
			size_t max_length = 0;

			traverse([&](
				const std::string& path,
				size_t path_length,
				size_t start,
				size_t end,
				const std::vector<size_t>& children_starts)
			{
				if (path_length > max_length)
				{
					max_length = path_length;
					max_path = path;
				}
			});

			return full_path(max_path);
		}

		std::string full_path(const std::string& path)
		{
			auto node = _root;
			std::string r;
			for (auto c : path)
			{
				auto child = node->children[c];
				r += _text.substr(child->start, *child->end - child->start);
				node = child;
			}
			return r;
		}

		void traverse(const std::function<void(
			const std::string& path,
			size_t path_length,
			size_t start,
			size_t end,
			const std::vector<size_t>& children_starts)>& callback)
		{
			struct item_t
			{
				std::string path;
				size_t length;
				nodeptr node;
				item_t(const std::string& path, size_t length, nodeptr node)
					: path(path), length(length), node(node)
				{}
			};

			std::list<item_t> queue;
			queue.push_back(item_t("", 0, _root));

			while (!queue.empty())
			{
				auto parent = queue.front();
				queue.pop_front();

				std::vector<size_t> starts;
				for (auto child : parent.node->children)
				{
					starts.push_back(child.second->start);
					if (child.second->children.size() == 0)
						continue;
					queue.push_back(
						item_t(
							parent.path + child.first,
							parent.length + *child.second->end - child.second->start,
							child.second));
				}
				if(parent.node != _root)
					callback(parent.path, parent.length, parent.node->start, *parent.node->end, starts);
			}
		}
	private:
		bool create_internal_node(nodeptr parent, size_t depth, size_t pos, std::shared_ptr<size_t> end)
		{
			nodeptr child;

			auto new_leaf = std::make_shared<node_t>(pos, end);

			while(child = parent->children[_text[pos - depth]])
			{
				auto edge_length = *child->end - child->start;
				if (edge_length > depth)
				{
					if (_text[child->start + depth] == _text[pos])
						return false;
					auto internal_node = std::make_shared<node_t>(
						child->start,
						std::make_shared<size_t>(child->start + depth));
					parent->children[_text[pos - depth]] = internal_node;
					child->start = *internal_node->end;
					internal_node->children[_text[*internal_node->end]] = child;
					internal_node->children[_text[pos]] = new_leaf;
					return true;
				}
				depth -= edge_length;
				parent = child;
			}
			parent->children[_text[pos - depth]] = new_leaf;
			return true;
		}
	};
}

namespace build_a_palindrome
{
	inline std::string solve(const std::string& a, const std::string& b)
	{
		std::string rb(b.crbegin(), b.crend());
		std::string c = a + "#" + rb + "$";
		auto pa = algorithm_lib::longest_palindromic_substring_t::max_lengths(a);
		auto pb = algorithm_lib::longest_palindromic_substring_t::max_lengths(rb);
		pa.push_back(0);
		pb.push_back(0);
		algorithm_lib::suffix_tree_t tree(c);

		std::string max_path;
		size_t max_length = 0;
		size_t max_start;

		auto construct_palidrome = [&](const std::string& path, size_t child_start)
		{
			auto full_path = tree.full_path(path);
			std::string palidrome;
			if (child_start <= a.size())
				palidrome = c.substr(child_start, pa[child_start]);
			else
				palidrome = c.substr(child_start, pb[child_start - 1 - a.size()]);
			return full_path + palidrome + std::string(full_path.crbegin(), full_path.crend());
		};

		tree.traverse([&](
			const std::string& path,
			size_t path_length,
			size_t start,
			size_t end,
			const std::vector<size_t>& children_starts)
		{
			size_t current_length = 0;
			std::string current_path;
			size_t current_start;
			bool left = false;
			bool right = false;
			for (auto start : children_starts)
			{
				size_t palindrome_length;

				if (start <= a.size())
				{
					left = true;
					palindrome_length = pa[start];
				}
				else
				{
					right = true;
					palindrome_length = pb[start - a.size() - 1];
				}

				auto length = path_length * 2 + palindrome_length;

				if (length < std::max(current_length, max_length))
					continue;

				if (length > current_length
					|| c[start] < c[current_start]
					|| c[start] == c[current_start] && c.substr(start, palindrome_length) < c.substr(current_start, palindrome_length))
				{
					current_length = length;
					current_path = path;
					current_start = start;
				}
			}

			if (false == left || false == right)
				return;

			if (current_length < max_length)
				return;

			if (current_length > max_length || construct_palidrome(current_path, current_start) < construct_palidrome(max_path, max_start))
			{
				max_length = current_length;
				max_path = current_path;
				max_start = current_start;
			}
		});
		return max_path.empty() ? "-1" : construct_palidrome(max_path, max_start);
	}

	inline void solve()
	{
		int t;
		std::cin >> t;
		while (t--)
		{
			std::string a, b;
			std::cin >> a >> b;
			std::cout << solve(a, b) << std::endl;
		}
	}
}

int main()
{
	build_a_palindrome::solve();
	return 0;
}

Build a Palindrome C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {

    /*
     * Complete the buildPalindrome function below.
     */
    static string buildPalindrome(string a, string b) {
         int max, n1 = a.Length, n2 = b.Length, c, size = 1, nn;

            max = 1;
            int[] poli1 = new int[n1];
            int[] poli2 = new int[n2];

            for (int i = 1; i < n1; i++)
            {
                nn = 1;
                poli1[i - 1] = 1;

                while (i + nn < n1 && i - nn >= 1 && a[i - nn] == a[i + nn])
                {
                    poli1[i - nn - 1] = 2 * nn + 1;
                    nn++;
                }

                nn = 1;
                while (i + nn < n1 && i - nn + 1 >= 1 && a[i - nn + 1] == a[i + nn])
                {
                    poli1[i - nn] = 2 * nn;
                    nn++;
                }
            }
            for (int i = n2 - 2; i >= 0; i--)
            {
                nn = 1;
                poli2[i + 1] = 1;

                while (i + nn < n2 - 1 && i - nn >= 0 && b[i - nn] == b[i + nn])
                {
                    poli2[i + nn + 1] = 2 * nn + 1;
                    nn++;
                }

                nn = 1;
                while (i - nn >= 0 && i + nn - 1 < n2 - 1 && b[i - nn] == b[i + nn - 1])
                {
                    poli2[i + nn] = 2 * nn;
                    nn++;
                }
            }

            string s1 = "", s2;


            var ar = new ValueTuple<int, int>[250000, 27];
            var dic = new int[n1+1];
            int previous = 0;
            a += '{';
            for (int i = 0; i < n1; i++)
            {
                int y = i, cur = 0;
                c = a[y] - 'a';

                if (ar[0, c].Item1 == 0)
                {
                    dic[i] = i;
                    ar[0, c] = (size, y);
                    size++;
                    continue;
                }
                else
                {

                    while (ar[cur, c].Item1 != 0)
                    {
                        previous = ar[cur, c].Item2;


                        if (poli1[previous] < poli1[y]) ar[cur, c].Item2 = y;
                        else if (poli1[previous] == poli1[y])
                            if (string.CompareOrdinal(a.Substring(previous + 1, poli1[previous]), a.Substring(y + 1, poli1[y])) > 0) ar[cur, c].Item2 = y;

                        cur = ar[cur, c].Item1;
                        y++;
                        c = a[y] - 'a';
                    }
                    while (a[y] == a[previous + 1])
                    {
                        c = a[y] - 'a';
                        int ek = poli1[previous + 1] > poli1[y] ? previous + 1 : poli1[previous + 1] < poli1[y] ? y : string.CompareOrdinal(a.Substring(previous + 2, poli1[previous + 1]), a.Substring(y + 1, poli1[y])) < 0 ? previous+1 : y;

                        ar[cur, c] = (size, ek);
                        cur = size;
                        size++;
                        y++;
                        previous++;
                    }
                    c = a[y] - 'a';

                    ar[cur, c] = (size, y);
                    dic[i] = y;

                    size++;
                    c = a[previous + 1] - 'a';
                    if (ar[cur, c].Item1 == 0)
                    {
                        ar[cur, c] = (size++, previous+1);
                        dic[previous+1 - y + i] = previous+1;
                    }
                }


            }
            nn = poli1.Max();
            var map = new Dictionary<int, ValueTuple<int, int, int>>();
            var tt = (0, 0, 0);
            map.Add(0, tt);
            int n3, n4, n5 = 0, z;
            size = 1;
            b = b.Insert(0, "{");
            for (int i = n2; i >= 1; i--)
            {
                c = b[i] - 'a';
                if (ar[0, c].Item1 == 0) continue;
                int cur = 0, j = i;

                while (ar[cur, c].Item1 != 0 && j != 0)
                {
                    n5 = ar[cur, c].Item2;
                    cur = ar[cur, c].Item1;
                    j--;
                    c = b[j] - 'a';
                }

                while (a[n5 + 1] == b[j] && j != 0)
                {
                    n5++;
                    j--;

                }
                n4 = i - j;


                if (n4 > 0)
                {
                    n3 = 2 * n4 + Math.Max(poli1[n5], poli2[j]);
                    if (n3 < max) continue;
                    else if (n3 > max)
                    {
                        n2 = Math.Max(n2, (max - nn) / 2);
                        map[0] = (n5, j, n4);
                        max = n3;
                        size = 1;
                    }
                    else if (n3 == max && size < map.Count)
                        map[size++] = (n5, j, n4);
                    else map.Add(size++, (n5, j, n4));
                }
                int pr = n5 - n4 + 2;
                while (dic[pr] <= n5 && pr < n1 && i > 0 )
                {
                    pr++;
                    i--;
                }

            }

            if (map[0].Item3 == 0) return "-1";
            n5 = map[0].Item1;
            z = map[0].Item2;
            n4 = map[0].Item3;
            
            int a1 = poli1[n5], a2 = poli2[z];
            s1 = a1 > a2 ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) :
            (a1 == a2 && string.CompareOrdinal(a.Substring(n5 + 1, a1), b.Substring(z - a2 + 1, a2)) < 0) ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) : string.Concat(a.Substring(n5 - n4 + 1, n4), b.Substring(z - a2 + 1, n4 + a2));

            while (size - 1 > 0)
            {
                n5 = map[size - 1].Item1;
            z = map[size - 1].Item2;
            n4 = map[size - 1].Item3;
                
                a1 = poli1[n5]; a2 = poli2[z];
                s2 = a1 > a2 ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) :
                (a1 == a2 && string.CompareOrdinal(a.Substring(n5 + 1, a1), b.Substring(z - a2 + 1, a2)) < 0) ? string.Concat(a.Substring(n5 - n4 + 1, n4 + a1), b.Substring(z + 1, n4)) : string.Concat(a.Substring(n5 - n4 + 1, n4), b.Substring(z - a2 + 1, n4 + a2));
                if (string.CompareOrdinal(s1, s2) > 0) s1 = s2;
                size--;

            }

            return s1;
        }
    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine());

        for (int tItr = 0; tItr < t; tItr++) {
            string a = Console.ReadLine();

            string b = Console.ReadLine();

            string result = buildPalindrome(a, b);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

Build a Palindrome Java Solution

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {

    static int N = 100000;
    static int M = 4 * N + 3;
    static char[] a = new char[M];
    static int[] sa = new int[M];
    static int[] isa = new int[M];

    static void iota(int v[], int end, int val) {
        for (int i = 0; i < end; i++) {
            v[i] = val++;
        }
    }

    static void suffixArray(int n, int m, int h[], int x[]) {
        Arrays.fill(h, 0, m, 0);
        for (int i = 0; i < n; i++) {
            isa[i] = a[i];
        }
        for (int i = 0; i < n; i++) {
            h[isa[i]]++;
        }
        for (int i = 1; i < m; i++) {
            h[i] += h[i - 1];
        }
        for (int i = n; --i >= 0; ) {
            sa[--h[isa[i]]] = i;
        }
        int k = 1;
        for (; ; k <<= 1) {
            iota(x, k, n - k);
            int j = k;
            for (int i = 0; i < n; i++) {
                if (sa[i] >= k) {
                    x[j++] = sa[i] - k;
                }
            }
            Arrays.fill(h, 0, m, 0);
            for (int i = 0; i < n; i++) {
                h[isa[x[i]]]++;
            }
            for (int i = 1; i < m; i++) {
                h[i] += h[i - 1];
            }
            for (int i = n; --i >= 0; ) {
                sa[--h[isa[x[i]]]] = x[i];
            }
            Arrays.fill(h, 0, m, 0);
            m = 1;
            h[sa[0]] = 0;
            for (int i = 1; i < n; i++) {
                if (isa[sa[i]] != isa[sa[i - 1]] || Math.max(sa[i], sa[i - 1]) >= n - k
                        || isa[sa[i] + k] != isa[sa[i - 1] + k]) {
                    m++;
                }
                h[sa[i]] = m - 1;
            }
            System.arraycopy(h, 0, isa, 0, n);
            if (m == n) {
                break;
            }
        }
        k = 0;
        h[0] = 0;
        for (int i = 0; i < n; i++) {
            if (isa[i] > 0) {
                for (int j = sa[isa[i] - 1]; i + k < n && j + k < n && a[i + k] == a[j + k]; k++)
                    ;
                h[isa[i]] = k;
                if (k > 0) {
                    k--;
                }
            }
        }
    }

    static int[][] tab = new int[19][M];

    static int lcp(int x, int y) {
        if (x < 0 || y < 0) {
            return 0;
        }
        x = isa[x];
        y = isa[y];
        if (x > y) {
            int t = x;
            x = y;
            y = t;
        }
        x++;
        int k = 0;
        while (1 << k + 1 < y - x + 1) {
            k++;
        }
        return Math.min(tab[k][x], tab[k][y - (1 << k) + 1]);
    }

    static long[] z = new long[2 * N + 1];
    static int[] len = new int[N];

    static void manacher(int from, int n) {
        int m = 2 * n + 1;
        z[0] = 1;
        for (int f = 0, g = 0, i = 1; i < m; i++) {
            if (i < g && z[2 * f - i] != g - i) {
                z[i] = Math.min(z[2 * f - i], g - i);
            } else {
                g = Math.max(g, f = i);
                for (; g < m && 2 * f - g >= 0 && (g % 2 == 0 || a[from + (2 * f - g) / 2] == a[from + g / 2]); g++) {
                    len[(g - 1) / 2] = g - f;
                }
                z[f] = g - f;
            }
        }
    }

    static int[] L = new int[M];
    static int[] R = new int[M];

    static char[] buildPalindrome(char[] a1, char[] b) {
        int na = a1.length;
        System.arraycopy(a1, 0, a, 0, na);
        a[na] = 0;
        int ra = na + 1;
        for (int i = 0; i < na; i++) {
            a[ra + i] = a[na - 1 - i];
        }
        a[ra + na] = 1;
        int nb = b.length;
        int b0 = ra + na + 1;
        System.arraycopy(b, 0, a, b0, nb);
        a[b0 + nb] = 2;
        int rb = b0 + nb + 1;
        for (int i = 0; i < nb; i++) {
            a[rb + i] = b[nb - 1 - i];
        }
        int n = 2 * na + 2 * nb + 3;
        suffixArray(n, 'z' + 1, tab[0], L);
        for (int i = 1; 1 << i < n; i++) {
            for (int j = n - (1 << i); j > 0; j--) {
                tab[i][j] = Math.min(tab[i - 1][j], tab[i - 1][j + (1 << i - 1)]);
            }
        }
        int bma = na + 1 + na + 1;
        for (int i = 0; i < n; i++) {
            if (bma <= sa[i] && sa[i] < bma + nb) {
                L[i] = sa[i];
            } else {
                L[i] = i > 0 ? L[i - 1] : -1;
            }
        }
        for (int i = n; --i >= 0; ) {
            if (bma <= sa[i] && sa[i] < bma + nb) {
                R[i] = sa[i];
            } else {
                R[i] = i + 1 < n ? R[i + 1] : -1;
            }
        }
        manacher(na + 1, na);
        int opt = 0;
        int optp = 0;
        int optx = 0;
        int opty = 0;

        for (int i = 0; i < na; i++) {
            int pal = i > 0 ? len[i - 1] : 0;
            int ii = na + 1 + i;
            int j = L[isa[ii]];
            if (lcp(ii, R[isa[ii]]) > lcp(ii, j))
                j = R[isa[ii]];
            int comm = lcp(ii, j);
            if (comm > 0) {
                int len = pal + 2 * comm;
                int pos = na - (i + comm);
                if (len > opt || len == opt && isa[pos] < isa[optp]) {
                    opt = len;
                    optp = pos;
                    optx = pal + comm;
                    opty = comm;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (na + 1 <= sa[i] && sa[i] < na + 1 + na) {
                L[i] = sa[i];
            } else {
                L[i] = i > 0 ? L[i - 1] : -1;
            }
        }
        for (int i = n; --i >= 0; ) {
            if (na + 1 <= sa[i] && sa[i] < na + 1 + na) {
                R[i] = sa[i];
            } else {
                R[i] = i + 1 < n ? R[i + 1] : -1;
            }
        }
        manacher(bma, nb);
        for (int i = 0; i < nb; i++) {
            int pal = i > 0 ? len[i - 1] : 0;
            int ii = bma + i;
            int j = L[isa[ii]];
            if (lcp(ii, R[isa[ii]]) > lcp(ii, j)) {
                j = R[isa[ii]];
            }
            int comm = lcp(ii, j);
            if (comm > 0) {
                int len = pal + 2 * comm, pos = n - (i + comm);
                if (len > opt || len == opt && isa[pos] < isa[optp]) {
                    opt = len;
                    optp = pos;
                    optx = comm;
                    opty = pal + comm;
                }
            }
        }

        if (opt == 0) {
            return "-1".toCharArray();
        }
        char[] result = new char[optx + opty];
        for (int i = 0; i < optx; i++) {
            result[i] = a[optp + i];
        }
        for (int i = 0; i < opty; i++) {
            result[optx + i] = a[optp + opty - i - 1];
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());

        for (int tItr = 0; tItr < t; tItr++) {
            char[] a = br.readLine().toCharArray();
            char[] b = br.readLine().toCharArray();

            bw.write(buildPalindrome(a, b));
            bw.newLine();
        }

        bw.close();
        br.close();
    }
}

Build a Palindrome JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'buildPalindrome' function below.
 *
 * The function is expected to return a STRING.
 * The function accepts following parameters:
 *  1. STRING a
 *  2. STRING b
 */
function State() {
  return {
    link: -1,
    posStart: 0,
    childs: {},
  };
}

function reverseString(str) {
  let res = '';
  for (let i = str.length - 1; i >= 0; i--) {
    res += str[i];
  }
  return res;
}

// Cut the string into characters and store the position of the character at the variable StateState
function buildState(a) {
  let states = Array.from({ length: 2 * a.length }, () => State()); //caching
  let last = 0,
    start = 1;
  for (let i = 0; i < a.length; i++) {
    const char = a[i];
    const cur = start;
    start++;
    states[cur].posStart = states[last].posStart + 1;
    let p = last;

    while (p !== -1 && !states[p].childs[char]) {
      states[p].childs[char] = cur;
      p = states[p].link;
    }

    if (p === -1) states[cur].link = 0;
    else {
      const q = states[p].childs[char];
      if (states[p].posStart + 1 === states[q].posStart) states[cur].link = q;
      else {
        const clone = start;
        start++;

        //copy older element state
        states[clone].posStart = states[p].posStart + 1;
        states[clone].childs = { ...states[q].childs };
        states[clone].link = states[q].link;

        while (p !== -1 && states[p].childs[char] === q) {
          states[p].childs[char] = clone;
          p = states[p].link;
        }
        states[q].link = clone;
        states[cur].link = clone;
      }
    }
    last = cur;
  }
  return states;
}
// build palindrome to look up
function lookupPalin(s) {
  const len = s.length;
  let sx = "|"; // cut the string into pieces: ex: |h|e|l|l|o|
  const sxlen = len * 2 + 1;
  for (let i = 0; i < len; i++) sx += s[i] + "|";

  let res = Array.from({ length: sxlen }, () => 0);

  let c = 0,
    r = 0,
    m = 0,
    n = 0;

  for (let i = 1; i < sxlen; i++) {
    if (i > r) {
      res[i] = 0;
      m = i - 1;
      n = i + 1;
    } else {
      const i2 = c * 2 - i;
      if (res[i2] < r - i) {
        res[i] = res[i2];
        m = -1;
      } else {
        res[i] = r - i;
        n = r + 1;
        m = i * 2 - n;
      }
    }
    while (m >= 0 && n < sxlen && sx[m] === sx[n]) {
      res[i] += 1;
      m -= 1;
      n += 1;
    }
    if (i + res[i] > r) {
      r = i + res[i];
      c = i;
    }
  }
  let result = Array.from({ length: len }, () => 0);
  for (let i = 1; i < sxlen - 1; i++) {
    const idx = parseInt((i - res[i]) / 2);
    result[idx] = Math.max(result[idx], res[i]);
  }
  return result;
}

// check ordre asc string
function check(s, initial, posStart, size) {
  for (let i = 0; i < size; i++) {
    if (s[initial + i] !== s[posStart + i]) {
      if (s[initial + i] > s[posStart + i]) return true; //
      break;
    }
  }
  return false;
}

function solve(a, b) {
  const blen = b.length;
  const states = buildState(a);

  let plookup = lookupPalin(b);

  let apos = 0,
    start = -1,
    left = 0,
    mid = 0,
    total = 0,
    curlen = 0;

  // find the position's index  of the palindrome start character
  for (let i = 0; i < blen; i++) {
    const char = b[i];
    if (!states[apos].childs[char]) {
      while (apos !== -1 && !states[apos].childs[char])
        apos = states[apos].link;
      if (apos === -1) {
        apos = 0;
        curlen = 0;
        continue;
      }
      curlen = states[apos].posStart;
    }

    curlen += 1;
    apos = states[apos].childs[char];
    const new_start = i - curlen + 1;
    let new_mid = 0;
    if (i + 1 < blen) new_mid = plookup[i + 1];
    const new_total = 2 * curlen + new_mid; //total length of such a substring palindrome

    if (
      total < new_total ||
      (total === new_total && check(b, start, new_start, curlen + mid))
    ) {
      left = curlen;
      mid = new_mid;
      total = new_total;
      start = new_start;
    }
  }

  // find palindrome
  let palindrome = [];
  for (let i = 0; i < left + mid; i++) palindrome.push(b[start + i]); // push string containt le palindrome
  for (let i = left - 1; i > -1; i--) palindrome.push(palindrome[i]); // push string can be reverse in other string
  return palindrome.join("");
}

function buildPalindrome(a, b) {
  const reverseB = reverseString(b);
  const res1 = solve(a, reverseB);
  const len1 = res1.length;
  const res2 = solve(reverseB, a);
  const len2 = res2.length;
  let res;
  if (len1 > len2) res = res1;
  else if (len1 < len2) res = res2;
  else res = res1 < res2 ? res1 : res2;
  if (res.length === 0) return -1;
  return res;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine().trim(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const a = readLine();

        const b = readLine();

        const result = buildPalindrome(a, b);

        ws.write(result + '\n');
    }

    ws.end();
}

Build a Palindrome Python Solution

def build_palindrome_lookup(s):
    sx = '|' + '|'.join(s) + '|'
    sxlen = len(sx)
    rslt = [0] * sxlen
    c, r, m, n = 0, 0, 0, 0
    for i in range(1, sxlen):
        if i > r:
            rslt[i] = 0
            m = i - 1
            n = i + 1
        else:
            i2 = c * 2 - i
            if rslt[i2] < r - i:
                rslt[i] = rslt[i2]
                m = -1
            else:
                rslt[i] = r - i
                n = r + 1
                m = i * 2 - n
        while m >= 0 and n < sxlen and sx[m] == sx[n]:
            rslt[i] += 1
            m -= 1
            n += 1
        if i + rslt[i] > r:
            r = i + rslt[i]
            c = i
    res = [0] * len(s)
    for i in range(1, sxlen - 1):
        idx = (i - rslt[i]) // 2
        res[idx] = max(res[idx], rslt[i])
    return res

class state:
    def __init__(self):
        self.link = -1
        self.length = 0
        self.childs = {}

def build_part_st(a, st, num, last, sz):
    for c in a:
        cur = sz
        sz += 1
        st[cur].length = st[last].length + 1
        p = last
        while p != -1 and c not in st[p].childs:
            st[p].childs[c] = cur
            p = st[p].link
        if p == -1:
            st[cur].link = 0
        else:
            q = st[p].childs[c]
            if st[p].length + 1 == st[q].length:
                st[cur].link = q
            else:
                clone = sz
                sz += 1
                st[clone].length = st[p].length + 1
                st[clone].childs = dict((x, y) for (x, y) in st[q].childs.items())
                st[clone].link = st[q].link
                while p != -1 and st[p].childs[c] == q:
                    st[p].childs[c] = clone
                    p = st[p].link
                st[q].link = clone
                st[cur].link = clone
        last = cur
    return last, sz

def print_st(st):
    i = 0
    for s in st:
        print('#{} link:{} childs:{}'.format(i, s.link, s.childs))
        i += 1

def solve(a, b):
    n = len(a)
    blen = len(b)
    st = [state() for x in range(2 * n)]
    st[0].link = -1
    st[0].length = 0
    last = 0
    sz = 1
    last, sz = build_part_st(a, st, 1, last, sz)
    plookup = build_palindrome_lookup(b)
    apos, start, left, mid, total, curlen = 0, -1, 0, 0, 0, 0
    for i in range(blen):
        c = b[i]
        if c not in st[apos].childs:
            while apos!=-1 and c not in st[apos].childs:
                apos = st[apos].link
            if apos == -1:
                apos = 0
                curlen=0
                continue
            curlen = st[apos].length
        curlen += 1
        apos = st[apos].childs[c]
        new_start = i - curlen + 1
        new_mid = 0
        if i + 1 < blen:
           new_mid = plookup[i + 1]
        new_total = 2 * curlen + new_mid
        if total < new_total or (total == new_total and lex_gt(b,start, new_start,curlen + mid)):
            left = curlen
            mid = new_mid
            total = new_total
            start = new_start
    palindrome = []
    for i in range(left + mid):
        palindrome.append(b[start + i])
    for i in range(left - 1, -1, -1):
        palindrome.append(palindrome[i])
    return ''.join(palindrome)
        
def lex_gt(s, old_start, new_start, size):
    for i in range(size):
        if s[old_start + i] != s[new_start + i]:
            if s[old_start + i] > s[new_start + i]:# old lex greater so pick new one
                return True
            break
    return False

def suffix_automata(a,b):
    rb = b[::-1] # reverse b
    rslt1 = solve(a, rb)
    rslt2 = solve(rb, a)
    rslt = None
    if len(rslt1) > len(rslt2):
        rslt = rslt1
    elif len(rslt1) < len(rslt2):
        rslt = rslt2
    else:
        rslt= rslt1 if rslt1 < rslt2 else rslt2
    if len(rslt) == 0:
        return '-1'
    return rslt

def process_helper(a,b):
    return suffix_automata(a,b)

for _ in range(int(input())):
    a = input()
    b = input()
    print(process_helper(a,b))

Other Solutions

c C# C++ HackerRank Solutions java javascript python

Leave a Reply