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;
}``````