dynamic_programming.longest_repeating_subsequence

Longest Repeating Subsequence (LRS)

Given a string, find the length of the longest repeating subsequence, i.e., the longest subsequence that occurs at least twice. The two occurrences must use characters at different positions in the original string.

This is a variation of the Longest Common Subsequence (LCS) problem where we find the LCS of the string with itself, with the constraint that characters at the same index position cannot both be used.

Reference: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Functions

longest_repeating_subsequence(→ int)

Find the length of the longest repeating subsequence in the given string.

Module Contents

dynamic_programming.longest_repeating_subsequence.longest_repeating_subsequence(string: str) → int

Find the length of the longest repeating subsequence in the given string.

A repeating subsequence is a subsequence that appears at least twice in the string, where characters at the same index are not counted as part of both subsequences simultaneously.

Uses dynamic programming with time complexity O(n^2) and space complexity O(n^2), where n is the length of the input string.

Parameters

stringstr

The input string to search for repeating subsequences.

Returns

int

The length of the longest repeating subsequence.

Examples

>>> longest_repeating_subsequence("aabb")
2
>>> longest_repeating_subsequence("aab")
1
>>> longest_repeating_subsequence("axxxy")
2
>>> longest_repeating_subsequence("abcabc")
3
>>> longest_repeating_subsequence("")
0
>>> longest_repeating_subsequence("a")
0
>>> longest_repeating_subsequence("abcdef")
0
>>> longest_repeating_subsequence("aaa")
2
>>> longest_repeating_subsequence("aaaa")
3
>>> longest_repeating_subsequence(12345)
Traceback (most recent call last):
    ...
TypeError: Input must be a string, got int