Repeated subsequence of length 2 or more

In the given string, find if there is any subsequence of length 2 0r more.
The sub-sequences should not have same character at same position.

Examples

a) Input string : ACBACE
    Output : Repeated subsequence exists.
    Here AC is repeated.

b) Input string : AAC
    Output : Repeated subsequence doesn`t exists.
    Here AC is repeated, but C is at same positions in both sub-sequences.

c) Input string : ABC
    Output : Repeated subsequence doesn`t exists.
    Here there is no subsequence with repeated strings.

Time complexity : O(n)

Algorithm

In this algorithm,

1.  We remove all the non-repeated characters from the string.

     a. Create an array to store the frequencies of characters.

     b. Traverse the input string and store the frequencies of all characters in the count array.

     c. If count of a character is more than 3, return true. (considering conditions like “AAA” which are palindrome but sub-sequence exists.)

     d. We in-place remove all non-repeating characters from the string.

2. Check if the resultant string is palindrome or not.

     a. If palindrome return false. Except if length is odd return true, if middle character is same as previous one.(“AAA” condition)

     b. Return true, if string is not palindrome.

C++ Program

#include <bits/stdc++.h>

#define MAX_CHAR 256
using namespace std;
 
//Function to check if given string is palindrome or not.
bool isPalindrome(char string[], int l, int h)
{
    while (h > l)
    {
        if (string[l++] != string[h--])
        {
            return false;
        }
    }
 
    return true;
}

int RepeatedSubsequenceCheck(char string[])
{
    int length = strlen(string);
    int count[MAX_CHAR] = { 0 };
    for (int i = 0; i < length; i++)//storing frequencies in count array
    {
        count[string[i]]++;
        //If character count is more than 3 we found repeatition.
        if (count[string[i]] > 3)
        {
            return true;
        }
    }
    // In-place remove non-repeating characters from the string
    int k = 0;
    for (int i = 0; i < length; i++)
    {
        if (count[string[i]] > 1)
        {
            string[k++] = string[i];
        }
    }
    string[k] = '\0';
    //check if the resultant string is palindrome
    if (isPalindrome(string, 0, k-1))
    {
        if (k & 1)//special case
        {
            return string[k/2] == string[k/2 - 1];
        }
        return false;// return false if string is a palindrome
        
    }
    return true; // return true if string is not a palindrome
}
 
//Main function
int main()
{
    char string[] = "ACBADC";
    if(RepeatedSubsequenceCheck(string))
    {
        cout<<"Repeated Subsequence Exists ("<<string<<")";
    }
    else
    {
        cout<<"Repeated Subsequence Doesn't Exists ("<<string<<")";
    }
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top