Question

link

Given a string, find if there is any sub-sequence that repeats itself. Do not reuse any char.

Eg:

1. abab <------yes, ab is repeated
2. abba <---- No, a and b follow different order 
3. acbdaghfb <-------- yes, a followed by b twice 
4. abcdacb <----- yes, a followed by b twice 

Note that no char should be reused. I.e. “aab” is a false.

Solution

This looks like a question without any clue. However, this actually is a modified version of [LintCode] Longest Common Subsequence.

Look at that question: there’s 2 input string, and they match char-by-char. For this question, we are simply matching input string with input string itself. And chars should be match ONLY at different positions, that’s the key. As pointed out by the top comment:

Now we can modify the longest_common_subsequence(a, a) to find the value of the longest repeated subsequence in a by excluding the cases when i == j

Code

public boolean checkRepeatSubseq(String input) {
    int len = input.length();
    int[][] dp = new int[len + 1][len + 1];
    // dp[i][j] denotes the length of subseq between 2 strings:
    // 1. first i chars of input
    // 2. first j chars of input
    for (int i = 1; i <= len; i++) {
        for (int j = i; j <= len; j++) {
            if (i != j && input.charAt(i - 1) == input.charAt(j - 1)) {
                int temp = Math.max(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = Math.max(temp, dp[i - 1][j - 1] + 1);
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[len][len] >= 2;
}