Check if repeated subsequence is present in the string or not

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.

For example,

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.

Below is C++ and Java implementation of the idea –

Java

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(n2).

(1 votes, average: 5.00 out of 5)