Untitled

 avatar
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