Given a string, check if repeated subsequence is present in the string or not. The repeated “subsequence” (not “substring”) should have length of 2 or more.

String XYBAXB has XB(XBXB) as repeated sub-sequence

String XBXAXB has XX(XXX) as repeated sub-sequence

String ABCA don’t have any repeated sub-sequence

String XYBYAXBY has XB(XBXB), XY(XYXY), YY(YYY), YB(YBYB) and YBY(YBYBY) as repeated subsequences

The idea is very simple. If we discard all non-repeating elements from the string (having frequency of 1) and the resulting string is non-Palindrome, then the string contains a repeated subsequence. If the resulting string is a palindrome and don’t have any character with frequency 3 or more, the string cannot have repeated subsequence.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <bits/stdc++.h> using namespace std; // Recursive function to check if str[low..high] is a // palindrome or not bool isPalindrome(string str, int low, int high) { // base case if (low >= high) return true; return (str[low] == str[high]) && isPalindrome(str, low + 1, high - 1); } // Function to checks if repeated subsequence is present // in the string bool repeatedSubsequence(string str) { // map to store frequency of each distinct character // of given string map<char, int> freq; // update map with frequency for (int i = 0; i < str.length(); i++) // if frequency of any character becomes 3, // we have found the repeated subsequence if (++freq[str[i]] >= 3) return true; string temp; // consider all repeated elements (frequency 2 or more) // and discard all non-repeating elements (frequency 1) for (int i = 0; i < str.length(); i++) if (freq[str[i]] >= 2) temp += str[i]; // return false if temp is a Palindrome return !isPalindrome(temp, 0, temp.length() - 1); } // main function int main() { string str = "XYBYAXB"; // XB and YB are repeated subsequence if (repeatedSubsequence(str)) cout << "Repeated Subsequence present"; else cout << "No Repeated Subsequence"; return 0; } |

**Output: **

Repeated Subsequence present

The time complexity of above solution is O(n^{}) where n is the length of the input string.

The problem can also be solved using Dynamic programming. It is nothing but variation of Longest Common Subsequence(LCS) problem. We will discuss DP solution in separate post. But the time complexity of DP solution is O(n^{2}).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply