Repeated subsequence of length 2 or more - GeeksforGeeks
Given a string, find if there is any subsequence of length 2 or more that repeats itself such that the two subsequence don't have same character at same position, i.e., any 0'th or 1st character in the two subsequences shouldn't have the same index in the original string.
Read full article from Repeated subsequence of length 2 or more - GeeksforGeeks
Given a string, find if there is any subsequence of length 2 or more that repeats itself such that the two subsequence don't have same character at same position, i.e., any 0'th or 1st character in the two subsequences shouldn't have the same index in the original string.
The problem is classic variation of longest common subsequence problem. We have discussed Dynamic programming solution here. Dynamic programming solution takes O(n2) time and space.
In this post, O(n) time and space approach is discussed.
The idea is to remove all the non-repeated characters from the string and check if the resultant string is palindrome or not. If the remaining string is palindrome then it is not repeated, else there is a repetition. One special case we need to handle for inputs like “AAA”, which are palindrome but their repeated subsequence exists. Repeated subsequence exists for a palindrome string if it is of odd length and its middle letter is same as left(or right) character.
bool
isPalindrome(
char
str[],
int
l,
int
h)
{
// l and h are leftmost and rightmost corners of str
// Keep comparing characters while they are same
while
(h > l)
if
(str[l++] != str[h--])
return
false
;
return
true
;
}
// The main function that checks if repeated
// subsequence exists in the string
int
check(
char
str[])
{
// Find length of input string
int
n =
strlen
(str);
// Create an array to store all characters and their
// frequencies in str[]
int
freq[MAX_CHAR] = { 0 };
// Traverse the input string and store frequencies
// of all characters in freq[] array.
for
(
int
i = 0; i < n; i++)
{
freq[str[i]]++;
// If the character count is more than 3
// we found a repetition
if
(freq[str[i]] > 3)
return
true
;
}
// In-place remove non-repeating characters
// from the string
int
k = 0;
for
(
int
i = 0; i < n; i++)
if
(freq[str[i]] > 1)
str[k++] = str[i];
str[k] =
'\0'
;
// check if the resultant string is palindrome
if
(isPalindrome(str, 0, k-1))
{
// special case - if length is odd
// return true if the middle characer is
// same as previous one
if
(k & 1)
return
str[k/2] == str[k/2 - 1];
// return false if string is a palindrome
return
false
;
}
// return true if string is not a palindrome
return
true
;
}