Discussion on Build a Palindrome Challenge

Sort by

recency

|

59 Discussions

|

7 days ago+ 0 comments

Hi HackerRank team,

I’m working on the “Build Longest Palindrome” problem and encountered an issue with Test Case 2.

My algorithm correctly constructs valid palindromes by combining substrings from a and b, and it passes all other cases. However, Test Case 2 expects a palindrome 'oozlzoo', which is not constructible from any combination of substrings from a and b — this violates the problem's core requirement.

I’ve verified this manually and through exhaustive debugging. Kindly review this test case for accuracy.

Thank you!

7 months ago+ 1 comment

This one is really annoying, because the description of the problem must be wrong. It specifically says find the longest s possible, and for the example given, the longest possible palindrome from substrings in bac bac, would be 'abba' or 'cbbc' (but I guess abba since it says if multiple exist choose the first alphabetically). aba is NOT the longest.

8 months ago+ 0 comments

I looked at the editorial but couldn't follow it. Here's my solution.

Prerequisites: Be able to create a suffix array from a string with LCP, be able to make RMQ queries on the LCP array, and implement Manacher's algorithm to find maximum palindromes.

Given two strings A and B, let revB = rev(B), and A' and B' are two substrings in A and revB where A' == B'. Then the solution will be the maximal length of the string where: A' + (palindrome in A after A') + B' OR B' + (palindrome in revB after B') + A'

We can handle both these cases by reversing B and independently finding the best result for A + rev(B) and rev(B) + A.

Let's solve for A, then we can find the final answer by swapping A and rev(B) and returning the best result.

First, we use Manacher's algorithm to give us an array of the max length of the palindromes starting at each index of a string. Manacher's algorithm gives us the maximal length of the palindrome centered at each index of a modified string of the form "|a|b|c|...|", so we can convert that into an array of the the maximal palindromes starting at the indexes of the original string "abc..." by changing coordinates, then fill in all non-maximal values:

fn longest_palindrome_by_start(s: &str) -> Vec<usize> {
    let lps = palindromes(s);
    let mut dp = vec![1; s.len()];
    for (i, &n) in lps.iter().enumerate().take(lps.len() - 1).skip(1) {
	// i:  12345
	// n: 0123210
	// j:  0 1 2
        //    |a|a|a|
        let j = (i - n) / 2;
        dp[j] = dp[j].max(n);
    }

    // dp now has all maximal palindromes by start. Fill in non-maximal values.
    let mut x = 1;
    for i in 0..dp.len() {
        if dp[i] >= x {
            x = dp[i];
        }
        dp[i] = x;
        if x > 2 {
            x -= 2;
        } else if x == 2 {
            x = 1;
        }
    }
    dp
}

Now we have lp = longest_palindrome_by_start(a).

Then, we compute a suffix array with LCP for "a$rev(b)", and a data structure to compute RMQ over the LCP. A solution palindrome looks like (substring of a) + (palidnrome in a after substring) + (substring of a in rev(b)). We have to find the lexicographically least solution palindrome of maximum length.

The suffix array gives us lexicographically ordered suffixes of the combined string "a$rev(b)". For every index in a, we need the maximum length of the common substring between a[i..] and b. To do that in lexicographical order, we maintain two pointers into the suffix array, left and right, which correspond to elements of the suffix array which are both in B. At each step, every element between left and right are all in A. For any i between left and right, the longest common substring between A and B is lcs = max(rmq[left + 1, i], rmq[i + 1, right]). Using this lcs, we can calculate the suffix_palindrome_len = lp[sa[i] + lcs], and the total palindrome length will be 2 * lcs + suffix_palindrome_len. We just track the max palindrome and return the first one which hits the max length:

fn solve_for_a<'a>(a: &'a str, b: &str) -> Option<Palindrome<'a>> {
    let lp = longest_palindrome_by_start(a);
    let combined = a
        .chars()
        .chain(std::iter::once('$'))
        .chain(b.chars())
        .map(|c| c as u8)
        .collect::<Vec<_>>();
    let sa = SuffixArray::new(&combined, 128).with_lcp();
    let rmq = RMQ::new(&sa.lcp);
    let n = a.len();

    let mut max_len = 0;
    let mut max_palindrome = None;

    // Maintain two pointers, left and right, to consecutive elements of sa which are in b.
    // For all elements of sa between left and right, left < i < right,
    // let prefix_len[i] = max(rmq[left + 1, i], rmq[i + 1, right])
    let mut left = sa.sa.iter().position(|&x| x > n).unwrap();
    while left < sa.sa.len() {
        let right = match sa.sa[left + 1..].iter().position(|&x| x > n) {
            Some(x) => left + 1 + x,
            None => sa.sa.len(),
        };
        for i in left + 1..right {
            // all i in a bounded by left and right in b.
            let j = sa.sa[i];
            let mut prefix_len = *rmq.get(left + 1, i);
            if right < sa.sa.len() {
                prefix_len = prefix_len.max(*rmq.get(i + 1, right));
            }
            if prefix_len == 0 {
                // no common substring
                continue;
            }
            let k = j + prefix_len;
            let suffix_len = if k < a.len() { lp[k] } else { 0 };
            let len = 2 * prefix_len + suffix_len;
            if len > max_len {
                max_len = len;

                max_palindrome = Some(Palindrome {
                    prefix: &a[j..k],
                    suffix: &a[k..k + suffix_len],
                });
            }
        }
        left = right;
    }

    max_palindrome
}

Note that we have to do this both for a + rev(b) and rev(b) + a and report out the max by length and lexicographical order.

11 months ago+ 0 comments

Java, Brute Force TLE version

  public static String buildAPalindrome(String a, String b) {
    String longest = "";
    for (int ai = 0; ai < a.length(); ai++) {
      StringBuilder aBuilder = new StringBuilder();
      for (int aj = ai; aj < a.length(); aj++) {
        aBuilder.append(a.charAt(aj));
        for (int bi = 0; bi < b.length(); bi++) {
          StringBuilder bBuilder = new StringBuilder();
          for (int bj = bi; bj < b.length(); bj++) {
            bBuilder.append(b.charAt(bj));
            String palindrome = aBuilder.toString() + bBuilder.toString();
            if (!palindrome.equals(new StringBuilder(palindrome).reverse().toString())) continue;
            if (
              palindrome.length() > longest.length()
              || (palindrome.length() == longest.length() && palindrome.compareTo(longest) < 0)
            ) {
              longest = palindrome;
            }
          }
        }
      }
    }
    return longest.isEmpty() ? "-1" : longest;
  }

1 year ago+ 1 comment

c++

#include <bits/stdc++.h>
using namespace std;

inline void wssert(bool b) { if(!b) exit(0); }

const string BAD = "-1";

const int MAXN = 2e5;
const int MAXM = 2e5;
const int MAXL = MAXN * 2 + MAXM * 2 + 20;
int N;
char A[MAXN];
int M;
char B[MAXM];
int L;
char V[MAXL];
int S;

int P[MAXL]; // length of palindrome - 1 / 2
int C[MAXL];

void manacher() {
    int c = 0, r = 0;
    memset(P, 0, sizeof(P));
    for(int i = 0; i < L; ) {
        assert(i - P[i] >= 0);
        assert(i + P[i] < L);
        assert(r == c + P[c]);
        assert(i >= c);
        assert(r >= i + P[i]);
        assert(i == c || r > i + P[i]);
        if(i == c) {
            assert(r == i + P[i]);
            if(i - P[i] - 1 >= 0 && i + P[i] + 1 < L && V[i - P[i] - 1] == V[i + P[i] + 1]) {
                P[i] ++;
                assert(i - P[i] >= 0);
                assert(i + P[i] < L);
            } else {
                i++;
                assert(P[i] == 0);
                assert(i - P[i] >= 0);
                assert(i == L || i + P[i] < L);
            }
       } else {
            assert(i > c);
            assert(r > i + P[i]);
            assert(c - P[c] >= 0);
            assert(c - (i - c) >= 0);
            int v = min(P[c - (i - c)], r - i);
            assert(v >= P[i]);
            if(v > P[i]) {
                P[i] = v;
                assert(i - P[i] >= 0);
                assert(i + P[i] < L);
            } else if (v == r - i) {
                assert(false);
            } else {
                i++;
                assert(P[i] == 0);
                assert(i - P[i] >= 0);
                assert(i == L || i + P[i] < L);
            }
        }
        if(i == L) break;
        if(i + P[i] >= r) {
            c = i;
            r = i + P[i];
        }
        assert(i - P[i] >= 0);
        assert(i + P[i] < L);
    }
}

#define REP(i, n) for(int i = 0; i < int(n); i++)
int gap;
int sa[MAXL], pos[MAXL], tmp[MAXL], lcp[MAXL];

bool sufCmp(int i, int j)
{
    if (pos[i] != pos[j])
        return pos[i] < pos[j];
    i += gap;
    j += gap;
    return (i < L && j < L) ? pos[i] < pos[j] : i > j;
}

void buildSA()
{
    REP(i, L) sa[i] = i, pos[i] = V[i];
    for (gap = 1;; gap *= 2)
    {
        sort(sa, sa + L, sufCmp);
        REP(i, L - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
        REP(i, L) pos[sa[i]] = tmp[i];
        if (tmp[L - 1] == L - 1) break;
    }
}

void buildLCP()
{
    for (int i = 0, k = 0; i < L; ++i) if (pos[i] != L - 1)
    {
        for (int j = sa[pos[i] + 1]; V[i + k] == V[j + k];)
            ++k;
        lcp[pos[i]] = k;
        if (k)--k;
    }
}

string process(int l, int c) {
    string res;
    for(int i = l; i < c; i++) {
        if(V[i] != 124) res += V[i];
    }
    for(int i = c; i >= l; i--) {
        if(V[i] != 124) res += V[i];
    }
    return res;
}

string go() {
    manacher();
    for(int i = 0; i < L; i++) {
        assert(!(i - P[i] - 1 >= 0 && i + P[i] + 1 < L && V[i - P[i] - 1] == V[i + P[i] + 1]));
        //for(int j = 0; j <= P[i]; j++) assert(V[i - j] == V[i + j]);
    }
    memset(C, 0, sizeof(C));
    for(int i = 0; i < L; i++) {
        C[i - P[i]] = max(C[i - P[i]], i);
    }
    for(int i = 1; i < L; i++) {
        C[i] = max(C[i], C[i - 1]);
    }
    buildSA();
    buildLCP();
    for(int i = 0; i < L; i++) {
        //cerr << (V + sa[i]) << '\n';
    }
    for(int i = 0; i + 1 < L; i++) {
        //for(int j = 0; j < lcp[i]; j++) assert(V[sa[i] + j] == V[sa[i + 1] + j]);
        assert(V[sa[i] + lcp[i]] < V[sa[i + 1] + lcp[i]]);
    }
    assert(V[sa[N + M]] == 123);
    int p[2] = {-1, -1};
    int l[2] = {0, 0};
    pair<int, int> res (0, 0);
    for(int i = 0; i < N + M; i++) {
        assert(V[sa[i]] < 123);
        bool d = (sa[i] >= S);
        p[d] = sa[i];
        l[d] = L;
        if(p[!d] != -1) {
            int match = l[!d];
            assert(match % 2 == 0);
            //cerr << p[!d] << ' ' << p[d] << ' ' << match << '\n';
            if(match) res = max(res, make_pair(C[sa[i] + match - 1] - sa[i], -i));
        }
        if(i + 1 < L) l[0] = min(lcp[i], l[0]), l[1] = min(lcp[i], l[1]);
    }
    p[0] = p[1] = -1;
    l[0] = l[1] = -1;
    for(int i = N + M - 1; i >= 0; i--) {
        bool d = (sa[i] >= S);
        p[d] = sa[i];
        l[d] = L;
        if(p[!d] != -1) {
            int match = l[!d];
            assert(match % 2 == 0);
            if(match) res = max(res, make_pair(C[sa[i] + match - 1] - sa[i], -i));
        }
        if(i > 0) l[0] = min(lcp[i - 1], l[0]), l[1] = min(lcp[i-1], l[1]);
    }
    //cerr << res << '\n';
    if(res.first == 0) return BAD;
    return process(sa[-res.second], sa[-res.second] + res.first);
}

int main() {
    int Q; cin >> Q;
    while(Q --> 0) {
        cin >> A >> B;
        N = strlen(A), M = strlen(B);
        L = 0;
        for(int i = 0; i < N; i++) {
            V[L++] = A[i];
            V[L++] = 124;
        }
        V[L++] = 123;
        V[L++] = 125;
        S = L;
        for(int i = M - 1; i >= 0; i--) {
            V[L++] = B[i];
            V[L++] = 124;
        }
        V[L] = 0;
        assert(L == 2 * N + 2 * M + 2);
        cout << go() << '\n';
    }
    return 0;
}

Sort by

|

59 Discussions

|

Cookie support is required to access HackerRank