C++ O(n^2) time /O(n) space solution without DP - Only check for subsequence len=2


#1

int Solution::anytwo(string A) {

 map<string,pair<int,int>> m;
// Check only for subseq with len =2
for(int i=1;i<A.size();++i)
{
    for(int j=0;j<i;++j)
    {
         string s="";
         s=s+A[j]+A[i];
        
        //if subseq s is present in m 
        if(m.find(s)!=m.end())
        {
            //check if it have same indexed character in the sequence
            //or check if two subsequences overlap
            // [1st subseq= present in map] [2nd subseq= s] 
            if(m[s].first!=j && m[s].second!=i )
            return 1;
            
        }
        //if subseq not present in map
        //insert into map with values of index of first and second char
        // Note : subseq of only two char so indexes stored in a pair
        else 
        {
            m[s].first=j;
            m[s].second=i;
        }
    }
}
//if no subseq of len two satisfy the question return 0
return 0;

}