Piyush_Paul_'s blog

Need Help with an Advanced Version of a Coding Test Question
By Piyush_Paul_, history, 5 days ago, In English

Hi everyone,

I recently participated in a coding test for a software development role and encountered an intriguing problem. It's an advanced version of the LeetCode question 2131. Longest Palindrome by Concatenating Two Letter Words.

For those unfamiliar with the original question, here's a brief description:

You are given an array of strings words. Each element of words consists of two lowercase English letters. Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

In the advanced version I faced, the constraints are relaxed so that words can be of any length, not just two letters. Here are a couple of examples to illustrate:

words = {"abab", "a"}: The longest palindrome that can be formed is "ababa" with a length of 5. words = {"ab", "aba", "xy"}: The longest palindrome that can be formed is "ababa" with a length of 5. The problem is challenging due to the added complexity of handling words of varying lengths. I would love to hear your thoughts and suggestions on how to approach solving this problem.

constraints:- 0<=words.length<=1000 0<=words[i]<=1000

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

To solve this problem, we need to form the longest palindrome using elements from the words array. Here's a structured approach to achieve this:

Steps to Solution: Understanding Palindrome Construction:

A palindrome reads the same forwards and backwards. To maximize its length, we can use characters symmetrically around a potential center. Character Frequency Count:

Count the frequency of each character (or each element in the case of strings) in the words array. Constructing the Palindrome:

For each element in words, add characters in pairs (or even number of times) to ensure they can form a palindrome. If there are any characters left with odd frequencies, we can use one of them as the central character of the palindrome (since a palindrome can have at most one odd-character frequency in its center). Implementation Strategy:

Count frequencies of characters (or strings). Accumulate pairs of characters (or strings). If there are characters left with odd frequencies, use one of them in the center of the palindrome. Calculate the length of the palindrome based on the accumulated pairs and the optional center character.

→ Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I hope, that it will be useful for you

    → Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I don't think that will help If I am thinking what you are thinking, can you get me an example to support your answer

    → Reply
  • »
    »
    5 days ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Why does it sound like its written by AI. Also you are telling to take the characters which are even in number from each string in the array and take them in the final answer to from a palindrome with taking atmost 1 odd character which we cannot do in the question asked. We are supposed to concatenate the strings to from a palindrome

    → Reply
    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The question came in the Online assessment conducted by DeShaw recently and adding to the point I never asked to take characters with even frequency from string, it can be and cannot be, eg1[ab, xyz, ba]-> abxyzba, eg2[aa, xy, aa]-> aaaa, eg3[mno, kmp, ababa, pp, qp]-> ababa, hope this might help you

      → Reply
      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I understood the question but the solution given by Bekbolot_Ubaidullaev is not correct. For instance , ["ab" , "bba" ] has the maximum palindrome length of 5 "abbba" but it will not give 5 as answer. Also in your eg1 , abxyzba is not a palindrome and the answer should be abba .

        → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it came in Salesforce OA recently instead of DE Shaw about which you mentioned in comments of the same blog

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007

int maxConcatenatedPalindrome(vector<string>& words){
    unordered_map<string, int> mp;
    int len = 0;
    bool hasOddPalindrome = false;

    for(string& word : words) mp[word]++;

    int x = -1;

    for(auto& pair : mp){
        string word = pair.first;
        int wordCount = pair.second;

        int n = word.length();

        string temp = word;
        reverse(temp.begin(), temp.end());

        if(word == temp){
            if(wordCount % 2 == 0){
                len += (wordCount * n);
            } 
            else{
                len += (wordCount - 1) * n;
                x = n;
                hasOddPalindrome = true;
            }
        } 
        else if(mp.find(temp) != mp.end()){
            int tempCount = mp[temp];
            int pairs = min(wordCount, tempCount);
            len += pairs * 2 * n;
            mp[temp] = 0;
        }
    }

    if(hasOddPalindrome) len += x; //middle

    return len;
}

int main() {
    vector<string> words1 = {"y", "xyx", "abc", "cba", "bac", "y", "y"};
    vector<string> words2 = {"y", "xyx", "abc", "cba", "bac", "y"};
    vector<string> words3 = {"ab", "ba", "xyx", "de"};
    vector<string> words4 = {"xy", "abc", "xyx", "bac", "cab", "cba"};

    cout << maxConcatenatedPalindrome(words1) << "\n";
    cout << maxConcatenatedPalindrome(words2) << "\n";
    cout << maxConcatenatedPalindrome(words3) << "\n";
    cout << maxConcatenatedPalindrome(words4) << "\n";

    return 0;
}
→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    {"abcd", "edc", "ba", "xyz", "pqr"} fails here-> abcd-edc-ba

    → Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Have anyone got the solution?

→ Reply