You are viewing a single comment's thread. Return to all comments →
Two pointers approach from a perspective different than the model solution:
int steadyGene(string gene) { unordered_map<char, int> freq; for (char c : gene) { ++freq[c]; } unordered_map<char, int> numChg; for (const auto& item : freq) { int chg = item.second - (int) gene.length() / 4; if (chg <= 0) {continue;} numChg[item.first] = chg; } if (numChg.empty()) {return 0;} int minLen = numeric_limits<int>::max(); freq.clear(); int l = 0; int r = 0; ++freq[gene[l]]; auto isOK = [&numChg, &freq]() { for (const auto& item : numChg) { if (item.second > freq[item.first]) {return false;} } return true; }; auto moveLeft = [&numChg, &freq, &gene, &l]() { if (!numChg.count(gene[l])) {return true;} if (freq[gene[l]] > numChg[gene[l]]) {return true;} return false; }; auto moveRight = [&numChg, &freq, &gene, &r, &moveLeft, &isOK]() { if (r >= gene.length() - 1) {return false;} if (!isOK()) {return true;} return !moveLeft() && r < gene.length() - 1; }; while (moveLeft() || moveRight()) { if (moveLeft ()) { --freq[gene[l++]]; } if (isOK()) {minLen = min(minLen, r - l + 1);} if (moveRight()) { ++freq[gene[++r]]; } } return minLen; }
Seems like cookies are disabled on this browser, please enable them to open this website
Bear and Steady Gene
You are viewing a single comment's thread. Return to all comments →
Two pointers approach from a perspective different than the model solution: