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.
I think I have an intuitive one. The key insight is to realize that you want the following invariant to hold: the count of A, T, G, and C outside the substring are all <= N / 4. Find the largest substring starting from 0 for which this holds. This is your right bound. Then try and make the substring smaller and smaller by increasing the left bound of the substring. If this makes the invariant false, you need to increase the right bound. For each left and right bound where the invariant holds, update your "best solution so far" if the distance between left and right is smaller. Once the right bound hits the end of the string, you have exhausted all possible solutions, return the best so far.
Bear and Steady Gene
You are viewing a single comment's thread. Return to all comments →
I think I have an intuitive one. The key insight is to realize that you want the following invariant to hold: the count of A, T, G, and C outside the substring are all <= N / 4. Find the largest substring starting from 0 for which this holds. This is your right bound. Then try and make the substring smaller and smaller by increasing the left bound of the substring. If this makes the invariant false, you need to increase the right bound. For each left and right bound where the invariant holds, update your "best solution so far" if the distance between left and right is smaller. Once the right bound hits the end of the string, you have exhausted all possible solutions, return the best so far.