Repeating Sub-Sequence

Given a string A, find if there is any subsequence that repeats itself.

A subsequence of a string is defined as a sequence of characters generated by deleting some characters in the string without changing the order of the remaining characters.

NOTE : sub-sequence length should be greater than or equal to 2.

The first and the only argument of input contains a string A.

Return an integer, 0 or 1:
    => 0 : False
    => 1 : True

1 <= length(A) <= 100

Input 1:
    A = "abab"

Output 1:
    1

Explanation 1:
    "ab" is repeated.

Input 2:
    A = "abba"
    
Output 2:
    0

Explanation 2:
    There is no repeating subsequence.

Method 1:

Use a set to keep track of chars we've seen so far, if we have seen a char twice, then remove all char before it, and add chars between the two occurrence, next time we see a char in the set, we know it's a subsequence repeating.

Solution 1:

Time: O(n^2)
Space: O(n)

public class Solution {
    public int anytwo(String A) {
        // abab
        // abab
       
        Set<Character> seen = new HashSet<>();
        boolean firstCharTwice = false;
        for (char c : A.toCharArray()) {
            if (!seen.contains(c)) {
                seen.add(c);
            } else if (firstCharTwice) {
                return 1;
            } else {
                firstCharTwice = true;
                seen.clear();
                seen.add(c);
                int i = A.indexOf(c) + 1;
                while (A.charAt(i) != c) {
                    seen.add(A.charAt(i));
                    i ++;
                }
            }
        }
        return 0;
    }
}
 
Method 2:
Apply longest common sebsequence on A, exception the subsequence cannot start at the same index.


Solution 2:

Time: O(n^2)
Space: O(n^2)

public class Solution {
    public int anytwo(String A) {
        int n = A.length();
        if (n == 0) return 0;
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (A.charAt(i - 1) == A.charAt(j - 1) && i != j) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][n] >= 2 ? 1 : 0;
    }
}

Space: O(n)

Space can be optimized.

public class Solution {
    public int anytwo(String A) {
        int n = A.length();
        if (n == 0) return 0;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i ++) {
            int temp = dp[0];
            for (int j = 1; j <= n; j ++) {
                int pre = temp;
                temp = dp[j];
                if (A.charAt(i - 1) == A.charAt(j - 1) && i != j) {
                    dp[j] = 1 + pre;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[n] >= 2 ? 1 : 0;
    }
}