Longest Repeated Subsequence | This function mainly returns LCS ( str , str ) with a condition that same characters at same index are not considered . ; This part of code is same as below post it fills dp [ ] [ ] https : www . geeksforgeeks . org / longest - repeating - subsequence / OR the code mentioned above ; This part of code finds the result string using dp [ ] [ ] Initialize result ; Traverse dp [ ] [ ] from bottom right ; If this cell is same as diagonally adjacent cell just above it , then same characters are present at str [ i - 1 ] and str [ j - 1 ] . Append any of them to result . ; Otherwise we move to the side that gave us maximum result . ; Since we traverse dp [ ] [ ] from bottom , we get result in reverse order . ; Driver Program
def longestRepeatedSubSeq ( str ) : NEW_LINE INDENT n = len ( str ) NEW_LINE dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( str [ i - 1 ] == str [ j - 1 ] and i != j ) : NEW_LINE INDENT dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = max ( dp [ i ] [ j - 1 ] , dp [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT res = ' ' NEW_LINE i = n NEW_LINE j = n NEW_LINE while ( i > 0 and j > 0 ) : NEW_LINE INDENT if ( dp [ i ] [ j ] == dp [ i - 1 ] [ j - 1 ] + 1 ) : NEW_LINE INDENT res += str [ i - 1 ] NEW_LINE i -= 1 NEW_LINE j -= 1 NEW_LINE DEDENT elif ( dp [ i ] [ j ] == dp [ i - 1 ] [ j ] ) : NEW_LINE INDENT i -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT j -= 1 NEW_LINE DEDENT DEDENT res = ' ' . join ( reversed ( res ) ) NEW_LINE return res NEW_LINE DEDENT str = ' AABEBCDD ' NEW_LINE print ( longestRepeatedSubSeq ( str ) ) NEW_LINE