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.
- Prepare
- Algorithms
- Strings
- Bear and Steady Gene
- Discussions
Bear and Steady Gene
Bear and Steady Gene
Sort by
recency
|
178 Discussions
|
Please Login in order to post a comment
include
using namespace std;
int test(int n, string s) { int required_count = n / 4; map mp; for (char it : s) { mp[it]++; } bool ok = true; for (auto tam : mp) { if (tam.second > required_count) { ok = false; break; } } if (ok) return 0; int min_val = n; int start = 0; for (int end = 0; end < n; end++) { mp[s[end]]--; while (mp['A'] <= required_count && mp['C'] <= required_count && mp['G'] <= required_count && mp['T'] <= required_count) { min_val = min(min_val, end - start + 1); mp[s[start]]++; start++; } } return min_val; }
int main() { int n; cin >> n; string s; cin >> s; cout << test(n, s) << endl; return 0; }
O(n) cpp solution, using two indices to keep track of min substrings, and pushing both indices until we find a new valid substring.
I find the optimal length of the substring to be replaced using binary search and for a given substring length I swipe through all possible substrings. The length of the substring to be replaced must be larger than the number of letters which I need to add to the rest of the string to compensate for the unequal number of letters in the latter. The solution scales as N*log(N)
thought this was a dynamic programming question, but turns out its just a simple log time search at each iteration algo.
O(n*log(n)) using lower bound
Haskell: