## Two Sigma Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Written Test

#include<bits/stdc++.h>

using namespace std;

set<string> dictionary_set;

int maxchain(string s,int i,int j)

{

if(i>j) return 0;

if(i==j&&dictionary_set.find(s)!=dictionary_set.end())

return s.size();

if(i==j) return 0;

int x=maxchain(s.substr(i+1,j),i+1,j);

int y=maxchain(s.substr(i,j-1),i,j-1);

int z=maxchain(s.substr(i+1,j-1),i+1,j-1);

x=x>y?x:y;

return x>z?x:y;

}

int main(){

string [] input={"a","b","ab","ac","abc"};

int max=0;

for(int i=0;i<input.size();i++)

dictionary_set.inset(input[i]);

for(int i=0;i<n;i++)

{

int x=maxchain(input[i],0,input[i].size()-1);

if(max<x)

max=x;

}

cout<<max<<endl;

return 0;

}

- Orion arm, Laniakea April 30, 2017