Shortest Uncommon Subsequence

Given two strings S and T, find length of the shortest subsequence in S which is not a subsequence in T. If no such subsequence is possible, return -1. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. A string of length n has different possible subsequences.

String S of length m (1 <= m <= 1000) String T of length n (1 <= n <= 1000)

Examples:

Input : S = “babab” T = “babba”
Output : 3
The subsequence “aab” of length 3 is 
present in S but not in T.

Input :  S = “abb” T = “abab”
Output : -1
There is no subsequence that is present 
in S but not in T.

class solution {
    public int solve(String S, String V) {
        int m = S.length(), n = V.length();
        // dp[i][j] -> Length of smallest uncommon substring between S.substring(0,i) & V.substring(0,j)
        int[][] dp = new int[m + 1][n + 1];
        // Base cases
        // 1) When length of V->0, then ans = 1
        for (int i = 0; i <= m; i++)
            dp[i][0] = 1;
        // 2) When length of S->0, then ans = Integer.MAX_VALUE
        for (int j = 0; j <= n; j++)
            dp[0][j] = 100001;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                // Finding the ith char of S, in V.substring(0,j)
                char c = S.charAt(i - 1);
                int index = -1;
                for (int z = j - 1; z >= 0; z--)
                    if (V.charAt(z) == c) {
                        index = z;
                        break;
                    }
                // If this char is unique to S.substring(0,i)
                // Then we can take this char only as our uncommon substring
                if (index == -1)
                    dp[i][j] = 1;
                // Otherwise we have 2 options
                else
                    // 1) Include the ith char in S & don't include it in V, by taking remaining answer from (i-1,index)
                    // 2) Don't include the ith char in S
                    dp[i][j] = Math.min(1 + dp[i - 1][index], dp[i - 1][j]);
            }
        }
        return dp[m][n];
    }
}