We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Hyper Strings
  5. Discussions

Hyper Strings

  • goelmanutv
     + 0 comments

    constexpr int MOD = 1'000'000'007;

    int hyperStrings(int m, const vector& H) { vector dp(m + 1, 0); dp[0] = 1;

    for (int len = 1; len <= m; ++len) {
    for (const auto& s : H) {
        int slen = s.size();
        if (slen <= len) {
            dp[len] = (dp[len] + dp[len - slen]) % MOD;
        }
    }
}

int64_t total = 0;
for (int val : dp)
    total = (total + val) % MOD;

return static_cast<int>(total);

    }

    int main() { vector H = { "cdefg", "bcei", "cdefghij", "abcg", "acdefj", "abcdehj", "aeghij", "bcdgh", "abcfhi", "begij", "bhij", "ab", "acghj", "abdhi", "f", "abcdefghj", "abchj", "gh", "bdefi", "chij", "fgj", "abcdefghij", "cdegj", "cghij", "acfg", "abcdfghij", "acdgi", "dehj", "abcdefhi", "cdfghj", "defhj", "bdfg", "de", "abdefgh", "abefj", "cdegh", "abi", "abdeij", "acdegh", "abdefgij", "cdefi", "acdh", "adefhij", "abci", "abdej", "bdfhij", "bdi", "cefgh", "acdefi", "acde", "bdegh", "di", "acefj", "abcdeghij", "ef", "abefgj", "acefij", "afij", "abdghi", "begi" };

    int m = 90;

int result = hyperStrings(m, H);

cout << result << "\n";

return 0;

    }

    The answer I am getting for Test Case 5 in Visual Studio 2022 is 555765527, While Expected is 929267708.

    Am I missing something here?