Check if a repeated subsequence is present in a string or not

Given a string, check if a repeated subsequence is present in it or not. The repeated subsequence should have a length of 2 or more.

For example,

String XYBAXB has XB(XBXB) as a repeated subsequence

String XBXAXB has XX(XXX) as a repeated subsequence

String ABCA doesn’t have any repeated subsequence

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

Practice this problem

The idea is 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 doesn’t have any character with frequency three or more, the string cannot have a repeated subsequence.

Following is the C++, Java, and Python implementation of the idea:

C++

#include <iostream>

#include <string>

#include <unordered_map>

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 hasRepeatedSubsequence(string str)

{

// base case

if (str.length() == 0) {

return false;

}

// map to store the frequency of each distinct character

// of a given string

unordered_map<char, int> freq;

// update map with frequency

for (int i = 0; i < str.length(); i++)

{

// if the 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);

}

int main()

{

string str = "XYBYAXB"; // 'XB' and 'YB' are repeated subsequences

if (hasRepeatedSubsequence(str)) {

cout << "Repeated subsequence is present";

}

else {

cout << "No repeated subsequence is present";

}

return 0;

}

Download Run Code

Output:

Repeated subsequence is present

Java

import java.util.HashMap;

import java.util.Map;

class Main

{

// Recursive function to check if `str[low…high]` is a palindrome or not

public static boolean isPalindrome(String str, int low, int high)

{

// base case

if (low >= high) {

return true;

}

return (str.charAt(low) == str.charAt(high)) &&

isPalindrome(str, low + 1, high - 1);

}

// Function to checks if repeated subsequence is present in the string

public static boolean hasRepeatedSubsequence(String str)

{

// base case

if (str == null || str.length() == 0) {

return false;

}

// map to store the frequency of each distinct character

// of a given string

Map<Character, Integer> freq = new HashMap<>();

// update map with frequency

for (char c: str.toCharArray())

{

freq.put(c, freq.getOrDefault(c, 0) + 1);

// if the frequency of any character becomes 3,

// we have found the repeated subsequence

if (freq.get(c) >= 3) {

return true;

}

StringBuilder sb = new StringBuilder();

// consider all repeated elements (frequency 2 or more)

// and discard all non-repeating elements (frequency 1)

for (char c: str.toCharArray())

{

if (freq.get(c) >= 2) {

sb.append(c);

}

// return false if `sb` is a palindrome

return !isPalindrome(sb.toString(), 0, sb.length() - 1);

}

public static void main(String[] args)

{

String str = "XYBYAXB"; // 'XB' and 'YB' are repeated subsequences

if (hasRepeatedSubsequence(str)) {

System.out.println("Repeated subsequence is present");

}

else {

System.out.println("No repeated subsequence is present");

}

Download Run Code

Output:

Repeated subsequence is present

Python

# Recursive function to check if `s[low…high]` is a palindrome or not

def isPalindrome(s):

(low, high) = (0, len(s) - 1)

while low < high:

if s[low] != s[high]:

return False

low = low + 1

high = high - 1

return True

# Function to checks if repeated subsequence is present in a string

def hasRepeatedSubsequence(s):

# base case

if not s:

return False

# dictionary to store the frequency of each distinct character of a given string

freq = {}

# update dictionary with frequency

for c in s:

# if the frequency of any character becomes 3, we have found a

# repeated subsequence

freq[c] = freq.get(c, 0) + 1

if freq.get(c) >= 3:

return True

# consider all repeated elements (frequency 2 or more)

# and discard all non-repeating elements (frequency 1)

repeated = [c for c in s if freq.get(c) >= 2]

# return false if it is a palindrome

return not isPalindrome(repeated)

if __name__ == '__main__':

s = 'XYBYAXB' # 'XB' and 'YB' are repeated subsequences

if hasRepeatedSubsequence(s):

print('Repeated subsequence is present')

else:

print('No repeated subsequence is present')

Download Run Code

Output:

Repeated subsequence is present

The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the length of the input string.

The problem can also be solved using dynamic programming. It is nothing but a variation of the Longest Common subsequence (LCS) problem. However, the time complexity of a dynamic programming solution is O(n²).