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];
}
}
