Given a string, find length of the longest repeating subsequence such that the two subsequence don’t have same string character at same position, i.e., anyith
character in the two subsequences shouldn’t have the same index in the original string.
Have you met this question in a real interview?
Yes
Example
str =abc
, return0
, There is no repeating subsequence
str =aab
, return1
, The two subsequence area
(first) anda
(second).
Note thatb
cannot be considered as part of subsequence as it would be at same index in both.
str =aabb
, return2
class Solution {
public:
/\*\*
\* @param str a string
\* @return the length of the longest repeating subsequence
\*/
int longestRepeatingSubsequence\(string& str\) {
// Write your code here
if \(str.empty\(\)\) {
return 0;
}
int n = str.length\(\);
vector<vector<int>> f\(n + 1, vector<int>\(n + 1, 0\)\);
for \(int i = 1; i <= n; ++i\) {
for \(int j = 1; j <= n; ++j\) {
if \(str\[i - 1\] == str\[j - 1\] && i != j\) {
f\[i\]\[j\] = f\[i - 1\]\[j - 1\] + 1;
} else {
f\[i\]\[j\] = max\(f\[i\]\[j - 1\], f\[i - 1\]\[j\]\);
}
}
}
return f\[n\]\[n\];
}
};