Repeated subsequence of length 2 or more | Python3 program to check if any repeated subsequence exists in the String ; A function to check if a String Str is palindrome ; l and h are leftmost and rightmost corners of Str Keep comparing characters while they are same ; The main function that checks if repeated subsequence exists in the String ; Find length of input String ; Create an array to store all characters and their frequencies in Str [ ] ; Traverse the input String and store frequencies of all characters in freq [ ] array . ; If the character count is more than 2 we found a repetition ; In - place remove non - repeating characters from the String ; check if the resultant String is palindrome ; special case - if length is odd return true if the middle character is same as previous one ; return false if String is a palindrome ; return true if String is not a palindrome ; Driver code
MAX_CHAR = 256 NEW_LINE def isPalindrome ( Str , l , h ) : NEW_LINE INDENT while ( h > l ) : NEW_LINE INDENT if ( Str [ l ] != Str [ h ] ) : NEW_LINE INDENT l += 1 NEW_LINE h -= 1 NEW_LINE return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def check ( Str ) : NEW_LINE INDENT n = len ( Str ) NEW_LINE freq = [ 0 for i in range ( MAX_CHAR ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq [ ord ( Str [ i ] ) ] += 1 NEW_LINE if ( freq [ ord ( Str [ i ] ) ] > 2 ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT k = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( freq [ ord ( Str [ i ] ) ] > 1 ) : NEW_LINE INDENT Str [ k ] = Str [ i ] NEW_LINE k += 1 NEW_LINE DEDENT DEDENT Str [ k ] = ' \0' NEW_LINE if ( isPalindrome ( Str , 0 , k - 1 ) ) : NEW_LINE INDENT if ( k & 1 ) : NEW_LINE INDENT return Str [ k // 2 ] == Str [ k // 2 - 1 ] NEW_LINE DEDENT return False NEW_LINE DEDENT return True NEW_LINE DEDENT S = " ABCABD " NEW_LINE Str = [ i for i in S ] NEW_LINE if ( check ( Str ) ) : NEW_LINE INDENT print ( " Repeated ▁ Subsequence ▁ Exists " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Repeated ▁ Subsequence ▁ Doesn ' t ▁ Exists " ) NEW_LINE DEDENT