## Google Interview Question for Software Engineer Interns

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
12
of 12 vote

We can implement this as a variation of the longest common subsequence in O(n^2), using dynamic programming. In the general problem, given two strings, 'a' and 'b', we find the longest common subsequence by computing a matrix M of size len(a)* len(b) defined as follows: M[ i ][ j ] is the value of the longest common subsequence between the strings "a0...ai" and "b0...bj". In particular, if a[ i ] == b[ j ], then M[ i ][ j ] = max (1 + M[ i-1 ][ j-1], M[ i - 1 ][ j ], M[ i ][ j-1 ]) , otherwise M[ i ][ j ] = max (M[ i - 1 ][ j ], M[ i ][ j-1 ]). The value of longest common subsequence is therefore M[ len(a) -1 ][ len(b) - 1].

Now we can modify the longest_common_subsequence(a, a) to find the value of the longest repeated subsequence in a by excluding the cases when i == j, (which we know are always equal in this case). Here is the code in python:

``````def longest_repeated_subsequence(a):
n = len(a)

M = [ [0] * n for i in range(n) ]

M[0][0] = 0

# First row
for j in range(1, n):
if a[0] == a[j]:
M[0][j] = 1
else: M[0][j] = M[0][j-1]

# First column
for i in range(1, n):
if a[i] == a[0]:
M[i][0] = 1
else: M[i][0] = M[i-1][0]

for i in range(1, n):
for j in range(1, n):
if a[i] == a[j] and i != j:
M[i][j] = max(
M[i-1][j-1] + 1, M[i-1][j], M[i][j-1])
else:
M[i][j] = max(M[i-1][j], M[i][j-1])

return M[n-1][n-1]``````

and, to test it:

``````def main():
strings = [
'abab',
'abba',
'acbdaghfb',
'abcdacb'
]

for s in strings:
print (longest_repeated_subsequence(s) > 1)``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

What do you mean when you say "The value of the longest common subsequence is therefore..."

Using your algorithm when I look at the result "M" of 'ababab' I get the following:

``````[a, b, a, b, a, b]
a [0, 0, 1, 1, 1, 1]
b [0, 0, 1, 2, 2, 2]
a [1, 1, 1, 2, 3, 3]
b [1, 2, 2, 2, 3, 4]
a [1, 2, 3, 3, 3, 4]
b [1, 2, 3, 4, 4, 4]``````

M[5][5] is 4. What is 4? 4 what?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

- chunxiaodiao2012: aabbcc is true since it contains subsequence abc repeated twice. same for aabb

Comment hidden because of low score. Click to expand.
0

@mc3po: M[5][5] = 4 is the length of the longest common subsequence (with the additional constraint of i != j); so in this case the sequence is 'abab--' and '--abab'. To output 'YES' is actually sufficient to find one subsequence with length > 2, so the code could be further optimized to stop as soon as it finds the first one. Obviously, the worst case running time it's still O(n^2)

Comment hidden because of low score. Click to expand.
0

I think this solution would not work with 'aaa' (it would detect a pair) - Although I am not sure about the requirement here...

Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the snippet

``````if a[i] == a[j] and i != j:
M[i][j] = max(
M[i-1][j-1] + 1, M[i-1][j], M[i][j-1])``````

can be reduced to

``````if a[i] == a[j] and i != j:
M[i][j] = M[i-1][j-1] + 1``````

For the same reason in Theorem 15.1(page 392) of the book, Introduction to Algorithm, 3rd Edition.

Comment hidden because of low score. Click to expand.
3
of 5 vote

This solution works O(n) time and O(n) memory. It can be trimmed to use O(1) memory as well. The trick is that if you remove the non repeated characters, the remaining should be palindrome (if it is not then for sure there is a repeated). Also even if it is palindrome with odd length you have to check that the middle letter is not different from its left or right.

You can count the letter and check for palndrom in O(n).

Step 1: Scan the string to count the number of each letter.
(mean while if the count of any letter is 4 or more, we already find a repetition of two character, the same character followed by itself and return YES)
If no character is repeated, return NO.

Step 2: Scan second time and append each letter that has been repeated (using the count array from the first step) to a new string (let say a StringBuilder)

Step 3: If the new string is not palindrom, return YES.
else if newString.length() is odd and the middle is different from one previous return YES.

return NO.

Comment hidden because of low score. Click to expand.
0

What about input "aabbc"? It should return false, But your step 2 gives "aabb", which is not a palindrome, and your step 3 gives true;

Comment hidden because of low score. Click to expand.
0

@Zen actually "aabbc" contains valid subsequence "ab"

Comment hidden because of low score. Click to expand.
0

what about 'aabcdddcbaa' ?

Comment hidden because of low score. Click to expand.
0

@Mando

The would still return true, the character 'a' has occurred 4 times (accounted for in Step 1 note).

Comment hidden because of low score. Click to expand.
0

Awesome solution!

Comment hidden because of low score. Click to expand.
1
of 1 vote

#include<iostream>
map <char,vector<int> >listE;

bool check(vector<int> a,vector<int> b)
{
if(a==b) return false;
if(a.size()!=b.size())return false;
for(unsigned int ii=0;ii<a.size();ii++)
{
if(a[ii]>b[ii])return false;
}
return true;
}

void printer(char s)
{
vector<int>a;a=listE[s];cout<<"\n Array \n";
for(unsigned int ii=0;ii<a.size();ii++)cout<<"\t"<<a[ii];
}

void removeDup(string s,string &s1)
{
for(unsigned int ii=0;ii<s.size();ii++)
{
if(s1.find(s[ii])!=string::npos)continue;
s1+=s[ii];
}
}
/*
if(check(listE[sin[ii]],listE[sin[ii+1]])){cout<<"\n Success:"<<sin[ii]<<"\t"<<sin[ii+1];}
else {cout<<"\n Not Success:"<<sin[ii]<<"\t"<<sin[ii];}
*/

bool looper(int ii,int jj,string sin)
{
if(check(listE[sin[ii]],listE[sin[jj]]))
{
cout<<"\n Success:"<<sin[ii]<<"\t"<<sin[jj];
for(unsigned int kk=ii+1;kk<sin.size();kk++)
{
looper(jj,kk,sin);

}
}

else {cout<<"\n Not Success:"<<sin[ii]<<"\t"<<sin[jj];return false;}
return true;

}

int main()
{
string s="abcdabacbc";string sin;

for(unsigned int ii=0;ii<s.size();ii++)
{
listE[s[ii]].push_back(ii);
}
removeDup(s,sin);

for(unsigned int ii=0;ii<sin.size()-1;ii++)
{
for(unsigned int jj=ii+1;ii<sin.size()-1;jj++)
{
cout<<"\n-----------\n";
looper(ii,jj,sin);
}
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about dp, saving first matching index, reusing dp array,
space - o(n), time - o(n2):

``````public static boolean repeatedSubsequence(String s) {
int dp[] = new int[s.length() + 1];
Arrays.fill(dp, -1);

for (int i = 1; i < s.length(); i++) {
for (int j = i + 1; j < s.length() + 1; j++) {
if (s.charAt(i - 1) != s.charAt(j - 1)) {
if (dp[j] == -1){
dp[j] = dp[j - 1];
}
} else {
if (dp[j - 1] == -1) {
dp[j] = i - 1;
} else {
if (s.charAt(dp[j - 1]) != s.charAt(j - 1)) {
return true;
} else {
dp[j] = dp[j - 1];
}
}
}
}
}

return false;``````

}

Comment hidden because of low score. Click to expand.
1
of 1 vote

Using a modification of Longest Common Subsequence algorithm we can solve it the following way:

``````public static int lcs(String str1, String str2, int m, int n, int length) {
if (length == 2) return length;
if (m == 0 || n == 0) return 0;
if (str1.charAt(m-1) == str2.charAt(n-1)) return lcs(str1, str2, m-1, n-1, length+1);
else return max(lcs(str1, str2, m, n-1, length), lcs(str1, str2, m-1, n, length));
}

public static int max(int a, int b) {
return (a > b)? a : b;
}

public static boolean repeatingSubsequence(String str) {
String str1 = "";
String str2 = "";

int i = 2;
while (i < str.length() - 1) {
str1 = str.substring(0, i);
str2 = str.substring(i);

if (lcs(str1, str2, str1.length(), str2.length(), 0) >= 2) {
return true;
}
i++;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0

This code is incorrect. For input "aabb" it gives false but it should be true.

Comment hidden because of low score. Click to expand.
1
of 1 vote

we can modify the longest_common_subsequence(a, a) to find the value of the longest repeated subsequence in a by excluding the cases when i == j, (which we know are always equal in this case). Here is the code in C++

``````int LongestRepeatedSubsequence(char* a, char* b) {
int n = strlen(a), m = strlen(b);

int len[n+1][m+1]     // should be dynamically allotted and freed

for(int i = 0; i < (n+1); ++i) {
for(int j = 0; j < (m+1); ++j) {
if(i==0 || j==0) len[i][j] = 0;
else {
if(a[i-1] == b[j-1] && i-1!=j-1) len[i][j] = 1 + len[i-1][j-1];
else len[i][j] = max(len[i-1][j], len[i][j-1]);
}
}
}

return len[n][m];
}

int main(int argc, char const *argv[])
{
char* str[] = {"abab", "abba", "acbdaghccfbc", "abcdacb"};

for(int i = 0; i < (int(sizeof(str)/sizeof(str[0]))); ++i) {
printf("%s - LRS = %d\n",str[i], LongestRepeatedSubsequence(str[i], str[i]) );
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

They are in the form of ascii value, traverse thru the string and store the index value when it matches with the same value in the string. Now check for the value between two indexes found and if its repeated after the second index.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//somewhat wild
static String givenLine;

public static void findSubSequence(String line) {
givenLine = line;

char char1;
char char2;

HashSet<String> possibleCombinations = new HashSet<String>();
for (int i = 0; i < line.length() - 1; i++) {
char1 = line.charAt(i);

for (int j = 0; j < line.length(); j++) {
char2 = line.charAt(j);

String combination = char1 + "" + char2;
if (char1 != char2 && !possibleCombinations.contains(combination)) {
System.out.println(char1 + ", " + char2 + " - " + repeats(char1, char2));
possibleCombinations.add(char1 + "" + char2);

}
}
}

}

public static boolean repeats(char char1, char char2) {
ArrayList<Integer> char1Occurences = new ArrayList<Integer>();
ArrayList<Integer> char2Occurences = new ArrayList<Integer>();

int indexOf1char = givenLine.indexOf(char1);

while (indexOf1char != -1) {
indexOf1char = givenLine.indexOf(char1, indexOf1char + 1);
}

int indexOf2char = givenLine.indexOf(char2);

while (indexOf2char != -1) {
indexOf2char = givenLine.indexOf(char2, indexOf2char + 1);
}

//        System.out.println(char1Occurences);
//        System.out.println(char2Occurences);

if (char1Occurences.size() < 2 || char2Occurences.size() < 2) {
return false;
}

int startIndex = 0;

ArrayList<Integer> bothIndeces = new ArrayList<Integer>();

while (startIndex < char1Occurences.size()) {
Integer char1Index = char1Occurences.remove(startIndex);
Integer char2Index = char2Occurences.remove(startIndex);

}

return isSorted(bothIndeces);

}

public static boolean isSorted(ArrayList<Integer> a) {
for (int i = 0; i < a.size() - 1; i++) {
if (a.get(i) > a.get(i + 1)) {
return false;
}
}

return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void FindPattern(const char* str, const int strLen, const char*& pattern, int& patternLen)
{
pattern = NULL;
patternLen = 0;

const int PATTERN_LEN = 2;
if(str == NULL || strLen <= PATTERN_LEN)
{
return;
}

for(int i = 0; i < (strLen - 1); i++)
{
const char* testPattern = &str[i];
for(int j = 0; j < (strLen - 1); j++)
{
if(i != j)
{
bool isMatch = true;
for(int k = 0; isMatch && k < PATTERN_LEN; k++)
{
isMatch = str[j+k] == testPattern[k];
}

if(isMatch)
{
pattern = testPattern;
patternLen = PATTERN_LEN;
return;
}
}
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.HashSet;

public class Main {

public boolean getRepeatedSequence(String input) {
char[] inputArray = input.toCharArray();
HashSet<String> subsetMatcher = new HashSet<String>();
StringBuilder buffer = new StringBuilder();
return recursiveSubSequence(inputArray, subsetMatcher, 0, buffer);
}

public boolean recursiveSubSequence(char [] inputArray, HashSet<String> subsetMatcher, int start, StringBuilder buffer) {
if(buffer.length() >= 2) {
if(subsetMatcher.contains(buffer.toString())) {
return true;
} else {
}
}
boolean result = false;
for(int i=start; i<inputArray.length; i++) {
buffer.append(inputArray[i]);
result = recursiveSubSequence(inputArray, subsetMatcher, i+1, buffer);
if(result == true) {
return true;
}
buffer.setLength(buffer.length()-1);
}

return false;
}

public static void main(String args[]) {
Main m = new Main();
System.out.println(m.getRepeatedSequence("abba"));
}
}``````

My solution is just take all the subsets and see if they are unique. Obviously the code doesn't work for "abba" as mentioned by the author of the post. I am not sure why abba is not valid. It has ab at two places {1,2} and {1,3} with b following a. So it's valid I guess.

However, if it is invalid, then I can store the indices that joined together to form the subset and then when comparing if there is repetition, I will check if the indices(first) in the two cases are same or not. For instance in the example string "abba", the first ab will have indices {1,2}, the second ab will have indices {1,3}. Since the first indices are same. I will regard them as different.

Has anyone better solution than this? Please let me know

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

bool repeat(const char *str) {
if(str == nullptr || strlen(str) < 4) return false;
unordered_map<char, vector<int>> indexList;
vector<char> twice;
int len = strlen(str);
for(int i = 0; i < len; i ++) {
indexList[str[i]].push_back(i);
if(indexList[str[i]].size() == 2) twice.push_back(str[i]);
}

for(int i = 0; i < twice.size(); i ++) {
for(int j = 0; j < twice.size(); j ++) {
if(i == j) {
if(indexList[twice[i]].size() >= 4) return true;
else continue;
} else {
int ii1 = indexList[twice[i]][0], ii2 = indexList[twice[i]][1];
int size = indexList[twice[j]].size();
int ij1 = indexList[twice[j]][size - 2], ij2 = indexList[twice[j]][size - 1];
if(ii1 < ij1 && ii2 < ij2) return true;
}
}
}
return false;
}

int main() {
cout << repeat("abab") << endl;
cout << repeat("abba") << endl;
cout << repeat("acbdaghfb") << endl;
cout << repeat("abcdacb") << endl;
return 0;
}``````

The complexity should be O(n^2)

Comment hidden because of low score. Click to expand.
0

It's a goo solution but i think you should have if(ii1 < ij1 && ii2 < ij2 && ii2 > ij1) instead of if(ii1 < ij1 && ii2 < ij2) to account for something like "aabb"

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool hasSubseq(string const &hSub) {
int hash[26][26];
memset(hash, 0, sizeof(hash));
int sz = hSub.size();

for(int i = 0; i < sz - 1; i++)
for(int j = i + 1; j < sz; j++)
hash[hSub[i] - 'a'][hSub[j] - 'a']++;

for(int i = 0; i < 26; i++) {
for(int j = 0; j < 26; j++) {
if(hash[i][j] >= 3)
return true;
}
}
return false;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````bool hasSubseq(string const &hSub) {
int hash[26][26];
int sz = hSub.size();
memset(hash, 0, sizeof(hash));

int ct = 3;
for(int i = 0; i < sz - 1; i++) {
for(int j = i + 1; j < sz; j++) {
hash[hSub[i] - 'a'][hSub[j] - 'a']++;
}
}

for(int i = 0; i < 26; i++) {
if(hash[i][i] >= 2) ct = 4;
}

for(int i = 0; i < 26; i++) {
for(int j = 0; j < 26; j++) {
if(hash[i][j] >= ct)
return true;
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution uses regex.

``````private static boolean matchPattern(String p,String ex)
{
ex=ex.replace("#",".+");
p=p.replaceFirst(ex,"");
if(p.equals(""))
{
return true;
}
return false;
}

public static void main(String[] args){

System.out.println(matchPattern("ABAB","A#B"));
System.out.println(matchPattern("abba","a#b"));
System.out.println(matchPattern("acbdaghfb","a#b"));
System.out.println(matchPattern("abcdacb","a#b"));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This question is very detailed, and that gives us the proper hint on handling this. The fact that the sequence can be dis-joined (not required to be continuous) allows us to utilize some neat tricks to keep run time and space complexity somewhat controlled. The size complexity of my solution is O(n) as it will require additional data structures that could be equal to the size of the original string plus the size of the known alphabet we are working with. The absolute worst case run-time would be O(n^2) in the event the character string was entered in alphabetical order and then reverse alphabetical order. This is unlikely to happen, but must be considered. Note that we will typically get better run time that this due to our ability to track unique characters by virtue of the Set interface. This will limit the number of full string scans to only those characters that actually have a duplicate, and will only do the full string scan one time for each possible duplicate.

Here is my coded Java solution with comments:

``````public boolean hasSequence(String s){
int[] alpha = new int[256];  //assumes ASCII char set
HashSet<Character> starts = new HashSet<Character>();

for(int i = 0; i < s.length(); i++){ //Scan string and load char counts into our alphabet array
alpha[s.charAt(i)]++;
}

for(int i = 0; i < 256; i++){  //find duplicate characters and identify them as possible sequence starters
if(alpha[i] > 1){
}
}

if(starts.size() == 0){  //if all chars distinct, fail fast
return false;
}

for(int i = 0; i < s.length(); i++){  //scan string stopping at known dupes/starts only
if( starts.contains( s.charAt(i) ) ){
HashSet<Character> seq = new HashSet<Character>();  //Create set to hold all distinct chars appearing after a known dupe/start
boolean secondStart = false;  //Flag to tell us if we have found the start again, used to identify if a sequence is present

for(int j = i+1;j < s.length(); j++){  //Scan characters after the known dupe/start and filling in a distinct set of those
if(!secondStart && s.charAt(j) == s.charAt(i) ){ secondStart = true; }

if( !seq.contains( s.charAt(j) ) ){  //If the character is not in the seq Set, add it
}
else if( seq.contains( s.charAt(j) ) && secondStart ){  //If character is in the Set AND we have found our start, then this is a sequence
return true;
}
}
}
starts.remove( s.charAt(i) );  //This start has no sequence, remove it from our scan
}

return false;
}``````

Note that this function could be further customized to accommodate the passing in of different alphabets to ensure modularity and re-usability, but for the sake of simplicity I have assumed an ASCII char set.

Comment hidden because of low score. Click to expand.
0

I think this may fail against the case of "aabac". You only tested for the case where the second start is adjacent to the first one. Further, the second start is added to seq, which is incorrect.

Comment hidden because of low score. Click to expand.
0
of 0 vote

"a" and "b" are used generically as any two distinct chars below.

If the question is asking for a binary output, the problem could be reduced to find a pattern of "abab" in any sebsequence. If found, the algorithm could break immediately.

Preprocessing: eliminate all unique chars, and put repeating chars in a hashmap (e.g. pos["a"] = [1,2,3]).

For each unordered pair in hahsmap, if any pos["a"][1]<pos["b"][1] and pos["a"][2]<pos["b"][-1], return True;
Return false

Space O(n) (ignoring hashmap overhead)
Time O(r^2) where r are number of repeating chars.

Note that each pair testing only takes O(1), the pair is unordered because if "abab" doesn't exist, "baba" can't exists.
We can safely use the first positions of a pair, because if the repeating sequence exists not using them, there are two cases: the first positions agree with the sequence order, we can switch to them, the first positions are reversed, so there must be something like "b....a....abab", so we are able to find "baba" anyway.

Comment hidden because of low score. Click to expand.
0

"For each unordered pair in hahsmap, if any pos["a"][1]<pos["b"][1] and pos["a"][2]<pos["b"][-1], return True;
Return false "

should be pos["a"][1] < pos["b"][-2] and pos["a"][2] < pos["b"][-1]

Comment hidden because of low score. Click to expand.
0

I made a mistake above. The check takes log(n) using a binary search such that b[0]<a[j]<b[-1] where 1<=j<a.size(). The O(1) check is buggy in some cases. and i don't think pos["a"][1] < pos["b"][-2] and pos["a"][2] < pos["b"][-1] is correct

Comment hidden because of low score. Click to expand.
0

Well I think it is easy to prove that my check is correct. But it is hard for me to prove in English. The simple idea is for 'a', 'b' (ordered), there are only two cases : .. a .. b .. a .. b .. or .. a .. a .. b .. b .. If a string as such two pairs, we replace two 'a' with the first two 'a', it still work. If we replace two 'b' with the last two 'b', it still work.

You can see my solution several comments above.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````boolean containsRepeatedSubSequence(char[] chars) {

if (chars.length < 4) { //by definition any string less than 4 chars is out
return false;
}

for (int i = 0; i < chars.length - 3; i++) { //search for a repeat of chars[i], stopping at 3rd to last char
int j;
for (j = i + 1; j < chars.length - 1; j++) {
if (chars[j] == chars[i]) {
break;
}
}
if (j == chars.length - 1) {
continue;
}
//char[i] and char[j] potentially contain the first character of a repeated subsequence
for (int k = i + 1; k < j; k++) {
for (int l = j + 1; l < chars.length; l++) {
if (chars[k] == chars[l]) {
return true;
}
}
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0

Hi,
I'm afraid the premise on the first comment may not be true:
"aaa" is a valid sequence for the purpose of the exercise

Comment hidden because of low score. Click to expand.
0

however 'aaa' (or any other <4 char sequence) cannot contain 2 pairs

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <cassert>

using namespace std;

class Solution
{
public:
unordered_map<char,vector<int> > countmap;
string st;
void makeMap(string st)
{
int l=st.length();
for (int i=0;i<l;++i)
{
countmap[st[i]].push_back(i);
}
}
bool repeatOrNot()
{
bool ans;
unordered_map<char,vector<int> >::iterator it,jt;
for (it=countmap.begin();it!=countmap.end();++it)
{
for (jt=countmap.begin();jt!=countmap.end();++jt)
{
ans=true;
cout<<jt->second.size()<<' '<<it->second.size()<<endl;
if (jt->second.size()!=it->second.size()) {ans=false;continue;}
int vil=jt->second.size();
if (vil<2) {ans=false;continue;}
for (int i=1;i<vil;++i)
{
if (((it->second)[i]-(jt->second)[i])*((it->second)[0]-(jt->second)[0])<=0) {ans=false;break;}
}
if (ans==true) return true;
}
}
return false;
}
};

int main()
{
Solution sol;
string st="aabcghxyzb";
sol.makeMap(st);
cout<<sol.repeatOrNot()<<endl;
return 0;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool customFindSubSeq(string ipStr)
{
vector<unsigned int> followedBy(26,0);
unsigned int toCheck = 0;

transform(ipStr.begin(), ipStr.end(), ipStr.begin(), ::tolower);

for (int i=0; i<ipStr.size(); i++) {
int index=(ipStr[i] - 'a');
unsigned int tmp = (1<<index);

if (toCheck != 0) {
for (int b=0; (b<32 && ((1<<b)<=toCheck)); b++)
{
if ( (1<<b) & toCheck) {
if ( followedBy[b] & tmp) {
return true;
}
}
}
}
for (int j=0; j<followedBy.size(); j++) {
if (followedBy[j] != 0)
followedBy[j] |= tmp;
}
if (followedBy[index] == 0)
followedBy[index] |= (1 << 31);
else
toCheck |= tmp;
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) match any pattern of char
add chars in map , from the string remove all the non repeated char
you will end up with string compare char neighbors if they are different it is subseq
if not try to remove the noise see how many char/pattern you have detect the false positive
and ignore it.

here is the solution

``````#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;

bool IsSubSequent(string s){
map<char,int> seqMap;
bool IsSubSeq=false;
string subSequent="";
for(char c: s){
if(seqMap.count(c)>0){
seqMap[c]+=1;

}
else{
seqMap[c]=1;
}
subSequent+=c;

}
int patternCount=0;
for(auto i: seqMap){
if(i.second==1){
subSequent.erase(subSequent.find(i.first),1);
}
else{
patternCount++;
}
}
char prev='\0',next='\0';

int falseCount=0;
for(char c : subSequent){
prev=next;
next=c;
if(prev=='\0' || next == '\0') continue;
if(prev==next)falseCount++;

}
IsSubSeq=falseCount<patternCount-1;
cout<<"*"<<subSequent<<"*";
return IsSubSeq;
}

int main(int argc, const char * argv[]) {

vector<string> v= {"abab","abba","acbdaghfb","abcdfdcab"};
for(string s : v){
cout<<s<<"=>"<<(IsSubSequent(s)?"true":"false")<<endl;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. have unordered_map<char, vector<int>> to have index of each character
2. iterate through the unordered_map and for every character which is having more than one index entry i.e. repeated, see if both indices > 0 or both indices < original string.size - 1. If it is then just grab the first or last char and this one and return that as the repeating subsequence. the thing is that if we have a repeating char and it is not at the start or at the end, there has to be some other char which can prefix or suffix the repeating char to form the repeating subsequence. This is O(n) assuming you use unordered_map and just iterate through all repeating char indices only once.

e.g.
abcb => has repeating char b => {1, 3} and both indices are > 0, so ab is repeating subsequence.
aba => repeating char a => {0, 2}, both are not > 0 neither are they less than size - 1 and hence it does not have a repeating subsequence
abac => repeating char a => {0, 2} here both are < size - 1 so subsequence repeating is ac

Comment hidden because of low score. Click to expand.
0
of 0 vote

only two chars in a string for example, we want to find whether "ab" is repeat
if the index of last "b" is after the index of 2nd "a" and the index of second last is after the index of 1st "a", "ab" is repeated.
We can enumerate every different two-chars-string.
Time complexity O(N)
Memory O(N)

``````boolean containRepeatString(string s){
vector<int> pos[26];
for (int i = 0; i < s.length; i++){
pos[s[i]-'a'].push_back(i);
}
for (char firstChar = 'a' ; firstChar <= 'z'; firstChar ++){
for (char secondChar = 'a'; secondChar <= 'z'; secondChar ++){
if (firstChar == secondChar) {
if (pos[firstChar].size() >= 4) cout << firstChar << secondChar << endl;
}
else{
if (pos[firstChar].size() >= 2 && pos[secondChar].size()>= 2){
if (pos[secondChar][pos[secondChar].size()-1] > pos[firstChar][1] && pos[secondChar][pos[secondChar].size()-2] > pos[firstChar][0]) {
cout << firstChar << secondChar << endl;
}
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since Question itself says. Check for every pair. My approach is take every out every pair store in hashmap along with index it uses and then look for if there exist same pair with different indices.

For eg:-
abab
1. ab in hashmap {{ab-> 0-1}} here key is ab and 0-1 is indices range
2. aa in hash map {{aa-> 0-2}}
3. ab in hash map. here you will see it is already in in hashmap. and if you look at the value it has same index as current index so we ignore this pair.
4. ba in hashmap {{ba->1-2 }}
5. bb in hashmap {{bb-> 1-3}}
6. ab here we again find it in hashmap. so we check if both indices differ they do. we found our solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static HashSet<string> set = new HashSet<string>();
static void Main(string[] args)
{
string s = "abc";

Console.WriteLine(IStringRepeating(s,1));
}

private static bool IStringRepeating(string s,int start)
{
if (s.Length < 2)
return false;

for(int i=0;i<s.Length-1;i++)
{
string str = s.Substring(i , 2);
if (set.Contains(str))
return true;
else
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package tests;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

public class TestSubSequence {

@Test
public void testSubSequece() {
assertTrue(containSubSequence("abab"));
assertTrue(containSubSequence("acbdalidb"));
assertFalse(containSubSequence("abba"));
assertTrue(containSubSequence("xxyy"));
assertTrue(containSubSequence("abcdabc"));
assertFalse(containSubSequence("abcdaxyz"));
}

public boolean containSubSequence(String s) {
Set<String> table = new HashSet<String>();
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
int sameCharIdx = 0;
for (int k = j + 1; k < s.length(); k++) {
if (s.charAt(k) == s.charAt(j) && sameCharIdx == 0) {
sameCharIdx = k;
}
if (sameCharIdx != 0) {
if (table.contains("" + s.charAt(j) + s.charAt(k))) {
return true;
}
}
table.add("" + s.charAt(j) + s.charAt(k));
}
}
table.clear();
}
return false;
}
}``````

Comment hidden because of low score. Click to expand.
0

it contains an extra loop. this is the corrected one:

``````public boolean containSubSequence(String s) {
Set<String> table = new HashSet<String>();
for (int i = 0; i < s.length(); i++) {
int sameCharIdx = 0;
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(j) == s.charAt(i) && sameCharIdx == 0)
sameCharIdx = j;

if (sameCharIdx != 0 && table.contains("" + s.charAt(i) + s.charAt(j)))
return true;

table.add("" + s.charAt(i) + s.charAt(j));
}
table.clear();
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.HashMap;
/*Given a string (1-d array) , find if there is any sub-sequence that repeats itself.
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice */
public class SubReaptArray {

public static void main(String[] args) {
String test ="abddabc";
//	System.out.println(test.indexOf("a",1));
SubReaptArray mSbucheck = new SubReaptArray();
System.out.println(mSbucheck.checkSubArray(test));

}

boolean checkSubArray(String input){
if(input.length()==1)
return false;
for(int i =0;i<input.length();i++){

char startValue = input.charAt(0);
int second = input.indexOf(startValue, i+1);
if(second == -1)
continue;
int third = input.indexOf(startValue, input.length()-1>second?second+1:second);
boolean value = checkRepeat(input,i,second, (third==-1)?input.length()-1:third);
if(value)
return true;
}

return false;

}
public boolean checkRepeat(String input, int start, int second, int third){
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(++start;start<second;start++){
map.put(input.charAt(start), 1);
}
for(++second;second<third;second++){
char mvalue = input.charAt(second);
if(map.containsKey(mvalue))
return true;
}
return false;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.HashMap;
/*Given a string (1-d array) , find if there is any sub-sequence that repeats itself.
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice */
public class SubReaptArray {

public static void main(String[] args) {
String test ="abddabc";
//	System.out.println(test.indexOf("a",1));
SubReaptArray mSbucheck = new SubReaptArray();
System.out.println(mSbucheck.checkSubArray(test));

}

boolean checkSubArray(String input){
if(input.length()==1)
return false;
for(int i =0;i<input.length();i++){

char startValue = input.charAt(0);
int second = input.indexOf(startValue, i+1);
if(second == -1)
continue;
int third = input.indexOf(startValue, input.length()-1>second?second+1:second);
boolean value = checkRepeat(input,i,second, (third==-1)?input.length()-1:third);
if(value)
return true;
}

return false;

}
public boolean checkRepeat(String input, int start, int second, int third){
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(++start;start<second;start++){
map.put(input.charAt(start), 1);
}
for(++second;second<third;second++){
char mvalue = input.charAt(second);
if(map.containsKey(mvalue))
return true;
}
return false;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the appear postion "First", "second" and "third".
And compare the value between ("First", "second") and ("second", "third"). Do they repeat or not!

``````import java.util.HashMap;
/*Given a string (1-d array) , find if there is any sub-sequence that repeats itself.
Here, sub-sequence can be a non-contiguous pattern, with the same relative order.

Eg:

1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order
3. acbdaghfb <-------- yes there is a followed by b at two places
4. abcdacb <----- yes a followed by b twice */
public class SubReaptArray {

public static void main(String[] args) {
String test ="abddabc";
//	System.out.println(test.indexOf("a",1));
SubReaptArray mSbucheck = new SubReaptArray();
System.out.println(mSbucheck.checkSubArray(test));

}

boolean checkSubArray(String input){
if(input.length()==1)
return false;
for(int i =0;i<input.length();i++){

char startValue = input.charAt(0);
int second = input.indexOf(startValue, i+1);
if(second == -1)
continue;
int third = input.indexOf(startValue, input.length()-1>second?second+1:second);
boolean value = checkRepeat(input,i,second, (third==-1)?input.length()-1:third);
if(value)
return true;
}

return false;

}
public boolean checkRepeat(String input, int start, int second, int third){
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(++start;start<second;start++){
map.put(input.charAt(start), 1);
}
for(++second;second<third;second++){
char mvalue = input.charAt(second);
if(map.containsKey(mvalue))
return true;
}
return false;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

static boolean find(String string, int startingIndex) {
if (startingIndex > string.length() - 1) return false;
int secondIndex = string.indexOf(string.charAt(startingIndex), startingIndex + 1);
if (secondIndex != -1) {
for (int i =1 ; i < secondIndex; i++) {
if (checkIfAvailable(string, string.charAt(startingIndex + i), secondIndex + 1)) {
return true;
}
}
} else {
return find(string, startingIndex + 1);
}
return false;
}

static boolean checkIfAvailable(String string, char ch, int index) {
return string.indexOf(ch, index) != -1;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static boolean find(String string, int startingIndex) {
if (startingIndex > string.length() - 1) return false;
int secondIndex = string.indexOf(string.charAt(startingIndex), startingIndex + 1);
if (secondIndex != -1) {
for (int i =1 ; i < secondIndex; i++) {
if (checkIfAvailable(string, string.charAt(startingIndex + i), secondIndex + 1)) {
return true;
}
}
} else {
return find(string, startingIndex + 1);
}
return false;
}

static boolean checkIfAvailable(String string, char ch, int index) {
return string.indexOf(ch, index) != -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.util.Scanner;

class SubStringOccurrence {
public static void main(String[] args) {
String str;
int flag = 0;
int i, j, k, l;
Scanner s = new Scanner(System.in);
str = s.next();

System.out.println("input String : "+str+ "\n");

// Rotate over array
for(i = 0; i < str.length()-1; i++){
for(j = i+1; j < str.length(); j++){
// first character out of 2 characters is found
if(j != str.length()-1 && str.charAt(i) == str.charAt(j)){
// Now search for second character from first half
// into second half
for(k = i+1; k < j; k++){
for(l = j+1; l < str.length(); l++){
if(str.charAt(k) == str.charAt(l)){
System.out.println(" "+str.charAt(i)+""+str.charAt(k)+ " is repeated");
flag = 1;
}
}
}

}
else{
continue;
}
}
}
if(flag == 0){
System.out.println("No substring found");
}
}
}``````

Comment hidden because of low score. Click to expand.
0

This code works perfectly fine.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Test {

public static void main(String args[])
{
String s = "acbghahk";
s ="abab";
s="abba";

int length = s.length();

for (int i = 0; i < length; i++) {

int ind = s.indexOf(s.charAt(i), i+1);

if(ind !=-1 && ind != length-1)
{
if(find(i, length, s, ind))
{

System.out.println("Yes");
return;
}

}

}

System.out.println("No");

}

private static boolean find(int charPos,int length,String str,int foundPos)
{
for (int i = charPos+1; i < foundPos+1; i++) {

int index = str.indexOf(str.charAt(charPos+1), foundPos+1);

if(index != -1)
{
return true;
}
charPos++;
}

return false;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Test {

public static void main(String args[])
{
String s = "acbghahk";
s ="abab";
s="abba";

int length = s.length();

for (int i = 0; i < length; i++) {

int ind = s.indexOf(s.charAt(i), i+1);

if(ind !=-1 && ind != length-1)
{
if(find(i, length, s, ind))
{

System.out.println("Yes");
return;
}

}

}

System.out.println("No");

}

private static boolean find(int charPos,int length,String str,int foundPos)
{
for (int i = charPos+1; i < foundPos+1; i++) {

int index = str.indexOf(str.charAt(charPos+1), foundPos+1);

if(index != -1)
{
return true;
}
charPos++;
}

return false;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ package string; import java.util.*; class StringTest1 { public static void main(String args[]) { Scanner scan=new Scanner(System.in); TreeSet<String> ts=new TreeSet<String>(); System.out.println("Enter the string"); String str=scan.next(); for(int i=0;i<str.length();i++) { for(int j=i+1;j<str.length();j++) { int x=str.indexOf(str.substring(i,j)); int y=str.lastIndexOf(str.substring(i,j)); if(x!=y&&str.substring(i,j).length()>1) ts.add(str.substring(i,j)); } } int count=0; System.out.println("The matches are...."); for(String s:ts) System.out.println("Match "+(++count)+"\t"+s); } } Eg: Enter the string xabyabyaxa The matches are.... Match 1 ab Match 2 aby Match 3 abya Match 4 by Match 5 bya Match 6 xa Match 7 ya
Comment hidden because of low score. Click to expand.
0
of 0 vote

A linear solution is implemented: Here is the pseudo-code:
- Detect each character's appearance. Return true, if any appears more than twice
- Strip out all characters that appear only once.
- Check if the rest string is palindrome. If yes, return false otherwise return true.

More details and explanation please refer to: cpluspluslearning-petert.blogspot.co.uk/2014/11/data-structure-and-algorithm-detect.html

``````#include <string>
#include <unordered_map>
#include <vector>

#include <cassert>

typedef std::unordered_map<size_t, size_t> FrequencyMap;

bool IsPalindrome(const std::string& myStr)
{
if (myStr.empty()) {
return false;
}

const size_t len = myStr.size();
if (len == 1) {
return true;
}

for (size_t start = 0, end = len - 1; start < end; ++start, --end) {
if (myStr[start] != myStr[end]) {
return false;
}
}

return true;
}

bool DetectFrequencyAndReturnFalseIGreaterThan2(const std::string& myStr, FrequencyMap& freqMap)
{
for (std::string::const_iterator cIt = myStr.begin(); cIt != myStr.end(); ++cIt) {
FrequencyMap::iterator found = freqMap.find(*cIt);
if (found == freqMap.end()) {
freqMap.insert(std::make_pair(*cIt, 1));
}
else {
++found->second;
if (found->second > 2) {
return true;
}
}
}

return false;
}

std::string StripCharsAppearingOnlyOnce(const std::string& myStr, const FrequencyMap& freqMap)
{
std::string result;
for (std::string::const_iterator cIt = myStr.begin(); cIt != myStr.end(); ++cIt) {
FrequencyMap::const_iterator found = freqMap.find(*cIt);
assert(found != freqMap.end());
if (found->second == 2) {
result.push_back(*cIt);
}
}

return result;
}

bool FindRepeatedSequence(const std::string& myStr)
{
FrequencyMap freqMap;
if (DetectFrequencyAndReturnFalseIGreaterThan2(myStr, freqMap)) {
return true;
}

std::string stringWithCharAppearingTwice = StripCharsAppearingOnlyOnce(myStr, freqMap);
if (stringWithCharAppearingTwice.empty() || stringWithCharAppearingTwice.size() == 1) {
return false;
}

return !IsPalindrome(stringWithCharAppearingTwice);
}

void TestCases()
{
assert(FindRepeatedSequence("aaa") == true);
assert(FindRepeatedSequence("abab") == true);
assert(FindRepeatedSequence("abba") == false);
assert(FindRepeatedSequence("acbdaghfb") == true);
assert(FindRepeatedSequence("abcdacb") == true);
}``````

Comment hidden because of low score. Click to expand.
0

A minor bug:

``````if (stringWithCharAppearingTwice.empty() || stringWithCharAppearingTwice.size() == 1) {
return false;
}``````

to

``````if (stringWithCharAppearingTwice.empty() || stringWithCharAppearingTwice.size() < 4) {
return false;
}``````

At least two different characters after strip out the characters that appears only once.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple regex expression:

``(.).*(.).*\1.*\2``

Forms two capture groups of one letter each, and sees if they reappear in the same order later on.

Comment hidden because of low score. Click to expand.
0
of 0 vote

you can combine suffix trees and DP together:

``````1. create a suffix tree.
2. search for the lowest node that splits - that's part of the longest repeated substring (count=node depth)
if the branching is for 2 strings (non of them is empty):
3. use common repeated substring between the two branches and add to the count.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a modification of Longest Common Subsequence algorithm we can solve it the following way:

``````public class RepeatingSubsequence {

public static int lcs(String str1, String str2, int m, int n, int length) {
if (length == 2) return length;
if (m == 0 || n == 0) return 0;
if (str1.charAt(m-1) == str2.charAt(n-1)) return lcs(str1, str2, m-1, n-1, length+1);
else return max(lcs(str1, str2, m, n-1, length), lcs(str1, str2, m-1, n, length));
}

public static int max(int a, int b) {
return (a > b)? a : b;
}

public static boolean repeatingSubsequence(String str) {
String str1 = "";
String str2 = "";

int i = 2;
while (i < str.length() - 1) {
str1 = str.substring(0, i);
str2 = str.substring(i);

if (lcs(str1, str2, str1.length(), str2.length(), 0) >= 2) {
return true;
}
i++;
}
return false;
}

public static void main (String [] args) {
System.out.println(repeatingSubsequence("abab") ^ true);
System.out.println(repeatingSubsequence("abba") ^ false);
System.out.println(repeatingSubsequence("abcb") ^ false);
System.out.println(repeatingSubsequence("aecbjbgha") ^ false);
System.out.println(repeatingSubsequence("aecbgbgha") ^ true);
System.out.println(repeatingSubsequence("xpyypx") ^ false);
System.out.println(repeatingSubsequence("aaaaaa") ^ true);
System.out.println(repeatingSubsequence("xxyy") ^ false);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// Asymptotic complexity - O(1) space, O(1) time. Not a joke :)

bool containsRepeating2CharSubsequence(const string& str)
{
const int alphabetSize = 26;
const int threshold = alphabetSize*2;
if (s.size() > threshold)
return true; // according to pigeonhole principle

int len = min(str.size(), threshold);

// let me write something purposefully ugly here to demonstrate
// that asymptotically it doesn't matter [still O(1) space, O(1) time] :)
for (int c1 = 0; c1 < len-3; c1++) {
for (int c2 = c1 + 1; c2 < len-2; c2++) {
for (int c3 = c2 + 1; c3 < len-1; c3++) {
if (str[c1]==str[c3]) {
for (int c4 = c3 + 1; c4 < len; c4++) {
if (str[c2] == str[c4]) return true;
}
}
}
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0

Can you clarify what is happening in your purposefully ugly code? Much obliged

Comment hidden because of low score. Click to expand.
0

Basically I wanted to show that it is not necessary to look at all input string - if string is long enough (larger than some constant threshold) then the result is 'true'. The constant threshold only depends on the alphabet size and doesn't depend on the length of the input string. So the key part of this "solution" is "if (s.size() > threshold) return true;"

Anything we do after this check doesn't depend on the input string length, so the running time of the "ugly" part is bound with some constant.

In this specific case the "ugly" part is just a brute-force search which checks for all combinations of pairs.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey this question can be solved in O(n) easily.
I'm assuming overlapping of the pairs is allowed.
Just maintain an array of number of occurrences of every letter before a certain index in an array like dp[i][c] i=index, c=character. And for every possible pair, once you find the second char add the number of occurences of the first char before the index.
Here's a working Java code

``````public int getTotal(String s) {
char[] in = s.toCharArray();
int n = in.length;
int[][] dp = new int[n][26];
for (int j = 0; j < 26; j++) {
if (in[0] - 'a' == j)
dp[0][j]++;
for (int i = 1; i < n; i++) {
dp[i][j] = dp[i - 1][j];
if (in[i] - 'a' == j)
dp[i][j]++;
}
}
int res = 0;
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
int occ = 0;
for (int k = n - 1; k > 0; k--) {
if (in[k] - 'a' == i) {
occ += dp[k - 1][j];
}
}
if (occ > 1){
System.out.println(((char)(j+'a'))+" "+((char)(i+'a')));
res += 1;}
}
}
return res;

}``````

Even a non overlapping version can be made by recursion. It would still be O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
using namespace std;

int main() {
string s="abcdacb";
int flag=0;
for(int i=0;i<s.length();i++)
{
for(int j=i+1;j<s.length()-1;j++)
{
if(s.at(i)==s.at(j)){

string st = s.substr(i+1,j-i-1);
for(int k = j+1;k<s.length();k++){
for(int f=0;f<st.length();f++){
if(st.at(f)==s.at(k)){
flag =1;
cout << "pattern found of "<< s.at(i) << st.at(f)<<"\n";
}
}
}
}

}

}
if(flag==0)
cout<< "no pattern found";
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) running time

``````public static boolean isRepeated(String input) {
for (int index = 0; index < input.length(); index++) {
Set<Character> container = new HashSet<Character>();
boolean firstTime = true;
char pick = input.charAt(index);
Set<Character> found = new HashSet<Character>();
System.out.println("pick = " + pick);
for (int sec = index + 1; sec < input.length(); sec++) {
char secChar = input.charAt(sec);
if (secChar == pick) {
if (firstTime) {
if (container.isEmpty()) {
break;
}
firstTime = false;
continue;
} else {
if (found.isEmpty()) {
break;
}
}

container = found;
firstTime = false;
found = new HashSet<Character>();
} else {
if (firstTime) {
} else {
if (container.contains(secChar)) {
}
}
}
}
if (found.size() > 0) {
return true;
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My understanding:
1. The problem just ask if any such subseq exist, so do DP with N^2 as longest common subseq is overkilling for this problem.
2. My idea is simple, if any exist, then a subseq with length of 2 must exist. Thus we just need to check any char pair (a,b) and see if it appears more than once in the string, using linear scan. Worst case would be O(26*26*n), assuming only lower-case chars in the string. Although with large constant, it's still linear.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string repeats(string s)
{
for(int i=0; i<s.length(); i++)
{
string::iterator first = s.begin()+i;

for(int j = i+1; j < s.length(); j++)
{
string::iterator second = s.begin()+j;
string::iterator search1 = first+1;
string::iterator search2 = second+1;

while(search1 != s.end() && search2 !=s.end())
{
while(search1 != s.end() && *search1 != *first)
{
search1++;
}

if(search1 != s.end())
{
if(*search1 == *first)
{
search2 = search1+1;
while(search2 != s.end() && *search2 != *second)
{
search2++;
}

if(search2 != s.end())
{
if(*search1 = *first && *search2 == *second)
{
return "YES";
}
}
}
}

}
}
}

return "NO";
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

DP is overcomplicating. Use greedy method. Setup a counter for each character, and sort them by their first appearance. While you are increasing any of the counter to 2, find if there is any counter before that has value greater than 1, if so, you have found a repeat.

``````def detectRepeatSeq(s):
counters = []

for c in s:
firstLetter = ''
if len(counters) < 1:
counters.append({'c': c, 'count': 1})
continue

for h in counters:
if h['c']==c:
if firstLetter != '':
return firstLetter + c
else:
h['count'] = h['count'] + 1
break

if h['count'] > 1:
firstLetter = h['c']
else:
counters.append({'c': c, 'count': 1})

return None

print detectRepeatSeq('abab')
print detectRepeatSeq('abba')
print detectRepeatSeq('acbdaghfb')
print detectRepeatSeq('abcdacb')
print detectRepeatSeq('aabb')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

DP is overcomplicating. Use an array of counters sorted by their first appearance. While you increase any of the counter to 2, check if there is any counter before that has value greater than 1. If so, you have found the repeat.

``````def detectRepeatSeq(s):
counters = []

for c in s:
firstLetter = ''
if len(counters) < 1:
counters.append({'c': c, 'count': 1})
continue

for h in counters:
if h['c']==c:
if firstLetter != '':
return firstLetter + c
else:
h['count'] = h['count'] + 1
break

if h['count'] > 1:
firstLetter = h['c']
else:
counters.append({'c': c, 'count': 1})

return None

print detectRepeatSeq('abab')
print detectRepeatSeq('abba')
print detectRepeatSeq('acbdaghfb')
print detectRepeatSeq('abcdacb')
print detectRepeatSeq('aabb')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Folks am I misunderstanding the problem or is it a very trivial state machine problem? All the good results match the regex /a.*b.*a.*b.*/. Regexes can all be trivially converted to an FSM, so that pattern matching can be done in O(n) with constant memory.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int findSubSequenceCount(String str, String subSeq)
{
if(str==null|subSeq==null)return 0;
if(subSeq.length()>str.length())return 0;
if(subSeq.equals(str))return 1;

int charTofind=0;
int subSeqLength=subSeq.length();
int foundCount=0;
for(int i=0;i<str.length();i++)
{
if(str.charAt(i)==subSeq.charAt(charTofind))
{
System.out.println(subSeq.charAt(charTofind)+"::"+str.charAt(i));
if(charTofind==subSeqLength-1)
{
System.out.println(charTofind);
foundCount++;
charTofind=0;
}
else
charTofind++;
}
}

return foundCount;
}

// Time complexity O(n) space constant.``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer is obviously

``1``

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool findIfSubSequesnce(string input)
{
map<char, int> m;
map<char, int>::iterator iter;
int i,j;
int len = strlen(input.c_str());
bool isCharRepeated=false;

/*

Step 1: Scan the string to count the number of each letter.
(mean while if the count of any letter
is 4 or more, we already find a repetition of two character, the same character followed by itself and return YES)
If no character is repeated, return NO.
*/

for (i = 0; i < len; i++)
{
iter = m.find(input[i]);
if (iter != m.end())
{
iter->second++;
isCharRepeated = true;
if (iter->second >= 4)
return true;
}
else
{
m.insert(pair<char, int>(input[i], 1));
}

}

if (!isCharRepeated)
return false;

/*
Step 2: Scan second time and append each letter that has been repeated (using the count array from the first step) to a new string (let say a StringBuilder)
*/

string str = "";
for (i = 0; i < len; i++)
{
iter = m.find(input[i]);
if (iter != m.end())
{
if (iter->second > 1)
str += input[i];
}
}

/*
Step 3: If the new string is not palindrom, return YES.
else if newString.length() is odd and the middle is different from one previous return YES.

return NO.
*/
len = strlen(str.c_str());
for (i = 0, j = len - 1; i < j; i++, j--)
{
if (str[i] != str[j])
return true;
}
if (i == j)
{
if (str[i - 1] != str[i])
return true;
else
return false;
}
else
return false;
}

int main(int argc, char* argv[])
{
bool ans = findIfSubSequesnce("abcdacb");
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
for i = 0; i < n; i++
var hashset = new Hashset<string>()
for j = i + 1; j < n; j++
if hashset.contains(input[i] + input[j])
return true
else hashset.insert(input[i] + input[j])
return false
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This works, O(N)

``````public static Boolean HasRepeatedSubstringPair(String s) {
HashSet hs = new HashSet();
for (Integer i = 1; i < s.length() -1; i++) {
Integer sum = (Integer)s.codePointAt(i-1) + s.codePointAt(i-1);
if (hs.contains(sum)) {
return true;
}
}
return false;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,

You can complete this problem by checking the value of index sum of all the repeating elements in the given string array.

``````public static boolean findSubsequent(String[] str ){
boolean result = false;
ArrayList<Integer> value_list = new ArrayList<Integer>();
ArrayList<Integer> sum_list = new ArrayList<Integer>();
int sum_val;
HashMap<String, List<Integer>> str_index = new HashMap<String, List<Integer>>();
int map_count = 0;
for(int i=0; i<str.length;i++){
if(str_index.containsKey(str[i])){
}
else
str_index.put(str[i], new ArrayList<Integer>(Arrays.asList(i)));
}
for(Map.Entry<String, List<Integer>> map_entry_check : str_index.entrySet()){
if(map_entry_check.getValue().size() >= 2){
map_count++;
}
}
if(map_count >= 2){
for(Map.Entry<String, List<Integer>> map_entry_check : str_index.entrySet()){
value_list.clear();
sum_val = 0;
for(int i=0; i<value_list.size();i++){
sum_val+=value_list.get(i);
}
}
for(int i=0; i<sum_list.size()-1; i++){
if((sum_list.get(i+1) - sum_list.get(i)) > 0){
result = true;
break;
}
}
}
else
result = false;
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time complexity. Tested code.:

``````public static void main(String[] args) {
String [] in = {"abab", "abba", "acbdaghfb", "abcdacb", "abbab", "abb", "abcddac", "abcddae"};
boolean [] expOut = {true, false, true, true, true, false, true, false};
Assert.assertEquals(in.length, expOut.length);
boolean [] out = new boolean[in.length];
HashMap<Character, Integer> charToFirstPosition = new HashMap<>();
for (int i = 0; i < in.length; i++) {
int leftCharPos = Integer.MAX_VALUE;
for (int j = 0; j < in[i].length(); j++) {
char c = in[i].charAt(j);
if (charToFirstPosition.putIfAbsent(c, j) != null) {
if (leftCharPos != Integer.MAX_VALUE && (charToFirstPosition.get(c) > leftCharPos)) {
out[i] = true;
break;
}
leftCharPos = Math.min(charToFirstPosition.get(c), leftCharPos);
}
}
charToFirstPosition.clear();
}
Assert.assertArrayEquals(expOut, out);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The idea is to basically find the longest comment subsequence (LCS) in s1 and s2 where s1 = s[0 ... i] and s2 = s[j ... k] where 0 <= i < j <= k.

Comment hidden because of low score. Click to expand.
0

This solution does not works for "xxyy". Because it find nothing but "xy" was repeated as the two characters doesn't need to be contiguous!

Comment hidden because of low score. Click to expand.
0
{{{I couldn't understand...

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.