Number of Strings Which Can Be Rearranged to Contain Substring
Intuition\n Describe your first thoughts on how to solve this problem. \nGiven the tree structure, the goal is to reduce the values in a manner that the total r
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGiven the tree structure, the goal is to reduce the values in a manner that the total reduction is minimized. By performing DFS, we can compute the necessary reductions for each subtree and ensure that the reduction for any node is done optimally by considering its children.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTree Representation: Convert the list of edges into an adjacency list representation of the tree.\nDFS Traversal: Perform a DFS traversal to compute the sum of values to be reduced from each node\'s subtree.\nReduction Calculation: At each node, calculate the sum of values to be reduced from its children. The value to be reduced at a node should be the minimum between the node\'s value and the sum of values to be reduced from its children.\n\n# Complexity\n- Time complexity: O(logn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n public:\n  int stringCount(int n) {\n    // There\'re three invalid conditions:\n    //   a. count(\'l\') == 0\n    //   b. count(\'e\') < 2\n    //   c. count(\'t\') == 0\n    //\n    // By Principle of Inclusion-Exclusion (PIE):\n    //   ans = allCount - a - b - c + ab + ac + bc - abc\n    const long allCount = modPow(26, n);\n    const long a = modPow(25, n);\n    const long b = modPow(25, n);\n    const long c = modPow(25, n) + n * modPow(25, n - 1);\n    const long ab = modPow(24, n) + n * modPow(24, n - 1);\n    const long ac = modPow(24, n);\n    const long bc = modPow(24, n) + n * modPow(24, n - 1);\n    const long abc = modPow(23, n) + n * modPow(23, n - 1);\n    return ((allCount - a - b - c + ab + ac + bc - abc) % kMod + kMod) % kMod;\n  }\n\n private:\n  static constexpr int kMod = 1\'000\'000\'007;\n\n  long modPow(long x, long n) {\n    if (n == 0)\n      return 1;\n    if (n % 2 == 1)\n      return x * modPow(x % kMod, (n - 1)) % kMod;\n    return modPow(x * x % kMod, (n / 2)) % kMod;\n  }\n};\n```
['Dynamic Programming', 'C++']