Untitled
unknown
plain_text
2 months ago
1.8 kB
3
Indexable
public class SecuredStrings { // Modulo value private static final long MOD = (long) 1e9 + 7; // Helper function to find the answer recursively private static long findAnswer(String s, String t, int n, int m, int i, int j, long[][] dp) { if (j == t.length()) { return (1L << (s.length() - i)) - 1; } if (i == s.length()) { return 0; } if (dp[i][j] != -1) { return dp[i][j] % MOD; } long count = 0; // Option 1: Skip the current character of string s count = (count + findAnswer(s, t, n, m, i + 1, j, dp)) % MOD; // Option 2: Compare current characters of s and t if (s.charAt(i) > t.charAt(j)) { count = (count + (1L << (s.length() - i - 1))) % MOD; } else if (s.charAt(i) == t.charAt(j)) { count = (count + findAnswer(s, t, n, m, i + 1, j + 1, dp)) % MOD; } return dp[i][j] = count % MOD; } // Function to calculate the number of secured strings public static int countSecuredStrings(String s, String t) { int n = s.length(); int m = t.length(); long[][] dp = new long[n + 1][m + 1]; // Initialize dp array with -1 for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { dp[i][j] = -1; } } // Call the helper function to get the answer return (int) (findAnswer(s, t, n, m, 0, 0, dp) % MOD); } public static void main(String[] args) { String s = "abc"; String t = "b"; System.out.println(countSecuredStrings(s, t)); // Example usage } }
Editor is loading...
Leave a Comment