Why there is a need for DP? Simple O(N) solution


#1
int Solution::anytwo(string A) {
unordered_map<char,int> mp;
int min_ind = INT_MAX; // Just store the min index of repeating char so that 
                       //whenever new repeating char comes whose index is more than 
                      //prev return 1;
for(int i=0 ; i<A.size() ; i++){
    if(mp.count(A[i])){
        if(mp[A[i]]>=min_ind){
            return 1;
        }
        else{
            min_ind = mp[A[i]];
        }
    }
    else{
        mp[A[i]] = i;
    }
}
return 0;

}


#2

explanation:

  1. sufficient condition to check is subsequence of length 2
  2. so allowed possibiliteies are
  • a…b…a…b
  • a…a…b…b
  • a…b…b…a is not allowed
  1. for the current character A[i] all we need to check is that first occurence of A[i] is after the first occurence of any previous character which occured twice.

#3

yeah u r right…but actually the problem tends to find the length of longest repeating subsequence at first,but after that I don’t know they just said to return 1 or 0…