Question

Goldman Sachs | OA | 2022 | Jewellery Design | Set - 42

Answer 1

Natalie is a famous jewellery designer, known for her pearl necklace designs. She has a team that helps her create unique designs made of different types of pearls. The team creates individual string of pearls, and Natalie then arranges the strings in a beautiful way to make necklace.
To begin with, Natalie prepares a rough sketch of the necklace by using a single character code to represent every pearl type she uses. The necklace design therefore looks like a series of strings in N different lines. Natalie's secret to making beautiful design to follow one specific rule. The rule is that two pearl strings can be consecutively arranged only if the two strings have a similar suffix chain such that length of the similar suffix chain is atmost one less than the length of the longer string i.e. two strings A and B are consecutively arranged only if LSC(A,B) >= max(|A|,|B|)-1 , where |A| indicates the length of string A.
Ex:
A: "gbpy"
B: "sbpy"
C:"bpy"
D:"bmy"
LSC(A,B)=max(|4|,|4|)-1=3
In this example atleast 3 suffix codes should exactly be same in A and B.
Her Team has brought in today's pearl strings, and Natalie is arranging them consecutively in necklace. She wants to create as big a necklace as possible. Write a program to help her arrange the longest possible sequence of strings, such that each two consecutive strings follow the rule.
Input:
4
gbpy
sbpy
bpy
bmy
Output:
3
Explanation:
Number of strings=4
Consider first 2 strings "gbpy" and "sbpy", they have 3 similar pearls in the suffix chain "bpy" hence LSC=3
Max(|4|,|4|)-1=4-1=3
Hence these 2 strings can be consecutively arranged.
Similarly both "gbpy" and "sbpy" can be arranged with "bpy" also. However the string "bmy" does not have a suffix chain similar enough with any other string to follow the rule.
Hence the longest possible arrangement is with 3 strings and the O/P is therefore 3.
Input 2:
5
rgb
ygb
mrwfna
gb
b
O/P:
4
The longest possible arrangement is with 4 strings
rgb
ygb
gb
b.
Please help me in solving this question.
If there is similar que related to it, comment it down below.

Answer 2

Somewhat similar to https://leetcode.com/problems/longest-string-chain/

I didn't consider some edge cases. Like the input list has duplications. I think counting the frequency of each word at the beginning could solve this.

 

class Jewellery:
    def jewelleryDesign(input):
        input.sort(key=lambda x: -len(x))
        res=0
        hasSeen=set()
        def dfs(word,length):
            nonlocal res
            if word:
                res=max(res,length)
            for char in "abcdefghijklmnopqrstuvwxyz ":
                new_word=char+word[1:]
                new_word=new_word.strip()
                if new_word in input and new_word not in hasSeen:
                    hasSeen.add(new_word)
                    dfs(new_word,length+1)

        for w in input:
            dfs(w,0)

        return res

a=['gbpy','sbpy','bpy','bmy']
print(Jewellery.jewelleryDesign(a))

 

Output is correct

This might work, this is basically LIS using strings

 

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
const ll maxn=200000+20;
const ll mod=1e9+7;
const ll m2=1e9+7;
const ll INF64 = ld(1e18);
const ll max2=1e3+10;
const ll N = 501;
const ll MAXN=2e5+10;
const ll ALPHABET_SIZE = 2;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

bool compare(string s1,string s2)
{
  return(s1.size()<s2.size());
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
//long long tt = clock();
#endif
ios_base::sync_with_stdio(NULL);  cin.tie(0); cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
cin>>n;
int i;
vector<string> v(n);
int sz=0;
set<string> s;
map<string,int> mp1,dp;
for(i=0;i<n;++i)
{cin>>v[i];
  //sz=max(sz,v[i].size());
  s.insert(v[i].substr(1,v[i].size()-1));
  dp[v[i].substr(1,v[i].size()-1)]++;
  mp1[v[i].substr(1,v[i].size()-1)]|=(1<<(v[i][0]-'a'));
}
vector<string> vf;
for(auto x:s)
  vf.push_back(x);

sort(vf.begin(),vf.end(),compare);
int ans=0;

for(auto x:vf)
{if(x=="")
continue;
  string sf=x.substr(1,sf.size()-1);
  char c=x[0];
  int x1=c-'a';
  if(dp.count(sf)!=0)
  {
    if((mp1[sf]&(1<<x1))!=0)
    {
      dp[x]+=dp[sf];
      ans=max(ans,dp[x]);
    }
  }

}
cout<<ans;
return(0);

}