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)

- koder November 08, 2014 | Flag Reply
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?

- mc3po December 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 0xF4 December 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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)

- koder December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 02, 2015 | Flag
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.

- xiaohan2012 February 22, 2015 | Flag
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.

- Mohammad October 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

- Zen October 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- zbdiablo March 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what about 'aabcdddcbaa' ?

- Mando Dong August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Mando

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

- Dave August 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome solution!

- Eric November 08, 2015 | Flag
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);
}
}
}

- jovi October 22, 2014 | Flag Reply
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;

}

- driv3r November 12, 2014 | Flag
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;
	}

- sfrizvi6 December 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 21, 2015 | Flag
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;
}

- sumanth232 December 23, 2014 | Flag Reply
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.

- manish.nayars October 22, 2014 | Flag Reply
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) {
            char1Occurences.add(indexOf1char);
            indexOf1char = givenLine.indexOf(char1, indexOf1char + 1);
        }

        int indexOf2char = givenLine.indexOf(char2);

        while (indexOf2char != -1) {
            char2Occurences.add(indexOf2char);
            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);

            bothIndeces.add(char1Index);
            bothIndeces.add(char2Index);
        }

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

- IgorBrown31 October 22, 2014 | Flag Reply
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;
				}
			}
		}
	}

}

- Anonymous October 22, 2014 | Flag Reply
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 {
				subsetMatcher.add(buffer.toString());
			}
		}
		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

- mikewhity October 22, 2014 | Flag Reply
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)

- Yihang Song October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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"

- abjee October 29, 2014 | Flag
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;
}

- Outermeasure October 23, 2014 | Flag Reply
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;
}

- Outermeasure- case aab October 23, 2014 | Flag
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"));
	}

- Algorithmy October 23, 2014 | Flag Reply
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){
				starts.add((char) i);
			}	
		}
		
		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
						seq.add( s.charAt(j) );
					}
					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.

- masterjaso October 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 24, 2014 | Flag
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.

- Anonymous October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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]

- NearSY.H October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- NearSY.H October 24, 2014 | Flag
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;
}

- Anonymous October 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Francesco October 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Flo January 02, 2015 | Flag
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;

}

- czhao86 October 26, 2014 | Flag Reply
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;
}

- JoyZombie October 26, 2014 | Flag Reply
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;
    }
}

- Dr.H October 28, 2014 | Flag Reply
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

- Girish October 29, 2014 | Flag Reply
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;
					}
				}
			}
		}
	}
   }

- mt October 30, 2014 | Flag Reply
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.

- Tester October 30, 2014 | Flag Reply
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
                    set.Add(str); 
            }

            return false;
        }

- Gurpreet Singh October 30, 2014 | Flag Reply
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;
	}
}

- Herve.Yuancheng November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Herve.Yuancheng November 02, 2014 | Flag
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;
	}
	
	
}

- fenghanlu November 11, 2014 | Flag Reply
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;
	}
	
	
}

- fenghanlu November 11, 2014 | Flag Reply
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;
	}
	
	
}

- fenghanlu November 11, 2014 | Flag Reply
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;
}

- Anonymous November 13, 2014 | Flag Reply
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;
    }

- Anonymous November 13, 2014 | Flag Reply
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");
		}
	}
}

- chavandp7 November 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This code works perfectly fine.

- chavandp7 November 18, 2014 | Flag
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;
	}
	
}

- BALA November 21, 2014 | Flag Reply
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;
	}
	
}

- BALA November 21, 2014 | Flag Reply
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 - Padmalochan November 25, 2014 | Flag Reply
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);
}

- Peter Tang November 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Peter Tang November 25, 2014 | Flag
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.

- Numsgil November 26, 2014 | Flag Reply
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.

- sagivo December 01, 2014 | Flag Reply
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("acebadb") ^ 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);
	}
}

- sfrizvi6 December 03, 2014 | Flag Reply
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; 
}

- 0xF4 December 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Questioner December 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- 0xF4 December 27, 2014 | Flag
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).

- renegade403 January 03, 2015 | Flag Reply
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;
}

- Sanchay Arora January 10, 2015 | Flag Reply
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) {
                        container.add(secChar);
                    } else {
                        if (container.contains(secChar)) {
                            found.add(secChar);
                        }
                    }
                }
            }
            if (found.size() > 0) {
                return true;
            }
        }
        return false;
    }

- hs February 08, 2015 | Flag Reply
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.

- fish266 February 26, 2015 | Flag Reply
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";
}

- Alex February 28, 2015 | Flag Reply
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')

- Chuck April 14, 2015 | Flag Reply
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')

- Chuck2015 April 14, 2015 | Flag Reply
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.

- Xenu June 29, 2015 | Flag Reply
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.

- udita1989 September 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer is obviously

1

- Anonymous September 24, 2015 | Flag Reply
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;
}

- diptivs December 19, 2015 | Flag Reply
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
}}

- om471987 June 12, 2016 | Flag Reply
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;
            }
            hs.add(sum);
        }
        return false;
    }

- Lvcaedivs aegyptii August 24, 2016 | Flag Reply
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])){
				str_index.get(str[i]).add(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;
				value_list.addAll(map_entry_check.getValue());
				for(int i=0; i<value_list.size();i++){
					sum_val+=value_list.get(i);
				}
				sum_list.add(sum_val);
			}
			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;
	}

- karthickgm27 January 10, 2017 | Flag Reply
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);
	}

- sauravsahu02 September 18, 2020 | Flag Reply
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.

- Anonymous October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Anonymous October 25, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes
{{{I couldn't understand... - yo October 26, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More