C# Solution for Get Equal Substrings Within Budget Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind using a prefix sum array and binary search is to efficiently calcu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind using a prefix sum array and binary search is to efficiently calculate the cost of transforming any substring of s to t and then use binary search to find the maximum length of a valid substring within the given cost constraint. By precomputing the prefix sums, we can quickly determine the cost of any substring in constant time, and binary search helps in efficiently finding the maximum length.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tCalculate Transformation Costs:\n\t\u2022\tCompute the absolute differences between corresponding characters in s and t and store these costs in an array called cost.\n2.\tPrefix Sum Array:\n\t\u2022\tConstruct a prefix sum array, prefixSum, where each element at index i represents the total cost to transform the substring from the start of the string to the i-th character.\n3.\tBinary Search for Maximum Length:\n\t\u2022\tFor each starting index i of a substring in s, use binary search to find the farthest ending index j such that the total transformation cost from i to j is within maxCost.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tPreprocessing Costs and Prefix Sum: O(n)\n\u2022\tCalculating the cost array and the prefixSum array each takes O(n) time.\n\u2022\tFinding Maximum Length: O(n \\log n)\n\u2022\tFor each starting position, we perform a binary search to find the maximum valid ending position, which takes O(\\log n). Since we do this for each of the n starting positions, the total time is O(n \\log n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tSpace for Arrays: O(n)\n\t\u2022\tWe use two additional arrays, cost and prefixSum, each of size n.\n\n# Code\n```\npublic class Solution {\n    public int EqualSubstring(string s, string t, int maxCost) {\n        int n = s.Length;\n        int[] cost = new int[n];\n        for (int i = 0; i < n; i++) {\n            cost[i] = Math.Abs(s[i] - t[i]);\n        }\n        \n        int[] prefixSum = new int[n + 1];\n        for (int i = 0; i < n; i++) {\n            prefixSum[i + 1] = prefixSum[i] + cost[i];\n        }\n        \n        int maxLength = 0;\n        for (int i = 0; i < n; i++) {\n            int low = i, high = n;\n            while (low < high) {\n                int mid = (low + high + 1) / 2;\n                if (prefixSum[mid] - prefixSum[i] <= maxCost) {\n                    low = mid;\n                } else {\n                    high = mid - 1;\n                }\n            }\n            maxLength = Math.Max(maxLength, low - i);\n        }\n        \n        return maxLength;\n    }\n}\n```
['C#']