Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: In-Person
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?
- chunxiaodiao2012: aabbcc is true since it contains subsequence abc repeated twice. same for aabb
@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)
I think this solution would not work with 'aaa' (it would detect a pair) - Although I am not sure about the requirement here...
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.
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;
@Mando
The would still return true, the character 'a' has occurred 4 times (accounted for in Step 1 note).
#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);
}
}
}
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;
}
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;
}
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;
}
//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;
}
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;
}
}
}
}
}
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
#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)
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;
}
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;
}
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"));
}
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.
"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.
"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]
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
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.
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;
}
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
#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;
}
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;
}
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;
}
}
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
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;
}
}
}
}
}
}
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.
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;
}
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;
}
}
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;
}
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;
}
}
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;
}
}
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;
}
}
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;
}
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;
}
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");
}
}
}
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;
}
}
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;
}
}
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);
}
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.
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.
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);
}
}
// 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;
}
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.
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).
#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;
}
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;
}
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.
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";
}
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')
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')
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.
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;
}
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;
}
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);
}
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.
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!
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:
and, to test it:
- koder November 08, 2014