Simple O(N^2) time and O(N) space solution


#1

In order to find the answer we need to find out whether repeating subsequence of length 2 exists.
Here is one of ways how we can do it:

bool shouldBeSkipped(vector<int> &positions, int pos){
    return positions.size() != 2 || positions[0] != pos;
}

bool shouldBeSkipped(vector<int> &positions1, vector<int> &positions2){
    return !(positions1[0] < positions2[0] && positions1[1] < positions2[1]);
}

int Solution::anytwo(string A) {
    map<char, vector<int>> symbolsTree;
    
    int N = A.length();
    for(int i = 0; i < N; i++){
        symbolsTree[A[i]].push_back(i);
        if(symbolsTree[A[i]].size() > 2)
            return true; // If any letter appears more than twice the result is always true
    }
    
    // If we are here all vectors in symbolsTree have exactly 2 or 1 size
    
    for(int i = 0; i < N; i++){
        vector<int> iPos = symbolsTree[A[i]];
        if(shouldBeSkipped(iPos, i))
            continue;
        
        for(int j = i + 1; j < N; j++){
            vector<int> jPos = symbolsTree[A[j]];
            if(shouldBeSkipped(jPos, j))
                continue;
                
            if(shouldBeSkipped(iPos, jPos))
                continue;
            
            return true;
        }
    }
    
    return false;
}