{"id":2308,"date":"2016-10-24T16:52:20","date_gmt":"2016-10-24T08:52:20","guid":{"rendered":"http:\/\/boweihe.me\/?p=2308"},"modified":"2016-10-24T16:52:20","modified_gmt":"2016-10-24T08:52:20","slug":"leetcode-424-longest-repeating-character-replacement","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2308","title":{"rendered":"LeetCode 424. Longest Repeating Character Replacement"},"content":{"rendered":"

\u601d\u8def\u5f88\u91cd\u8981\u3002
\n\u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6n\u7684\u5b57\u7b26\u4e32s\u548c\u9650\u5236k\uff0c\u5c06s\u4e2d\u7684\u90e8\u5206\u5b57\u7b26\u66ff\u6362(\u66ff\u6362\u6b21\u6570<=k)\u540e\uff0c\u80fd\u5f97\u5230\u8fde\u7eed\u5b57\u7b26\uff08\u5982AAAA\uff09\u7684\u957f\u5ea6\u6700\u5927\u4e3a\u591a\u5c11\uff1f
\n\u4f7f\u7528\u6ed1\u52a8\u7a97\u53e3\u7684\u601d\u8def\u53ef\u4ee5\u5728O(n)\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u60c5\u51b5\u4e0b\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u3002\u9700\u8981\u8bb0\u5f55\u5f53\u524d\u7a97\u53e3\u5185\u5404\u4e2a\u5b57\u7b26\u7684\u8ba1\u6570\u503c\uff08\u53ef\u4ee5\u770b\u505a\u5206\u5e03\u60c5\u51b5\uff09\u4ee5\u53ca\u5f53\u524d\u7a97\u53e3\u7684\u8d77\u59cb\u70b9\uff0c\u7a97\u53e3\u5185\u6700\u591a\u5b57\u7b26\u7684\u8ba1\u6570best\u3002\u6211\u4eec\u77e5\u9053\uff0c\u6700\u591a\u5b57\u7b26\u7684\u8ba1\u6570best+\u4fee\u6539\u6570\u91cfk\u5982\u679c\u8fd8\u662f\u4e0d\u80fd\u4f7f\u5f97\u5f53\u524d\u7a97\u53e3\u5185\u7684\u5b57\u7b26\u90fd\u7edf\u4e00\u7684\u8bdd\uff0c\u5c31\u5f97\u628a\u7a97\u53e3\u7f29\u5c0f\uff08\u8d77\u59cb\u70b9\u540e\u632a\uff09\u3002\u7a97\u53e3\u7f29\u5c0f\u65f6\u8bb0\u5f97\u628a\u7a97\u53e3\u8ba1\u6570\u66f4\u65b0\u4e00\u4e0b\u3002
\n\u8fd9\u91cc\u6709\u4e00\u4e2atricky\u7684\u5730\u65b9\uff0cbest\u503c\u672c\u6765\u5728\u6ed1\u52a8\u7a97\u53e3\u7684\u65f6\u5019\u662f\u8981\u66f4\u65b0\u7684\uff0c\u56e0\u4e3a\u53ef\u80fd\u7a97\u53e3\u8fc7\u4e86\u8fd9\u4e2abest\u4f1a\u53d8\u5c0f\u3002\u4f46\u662f\u7531\u4e8e\u6211\u4eec\u8981\u627e\u7684\u53ea\u662f\u4e2a\u6700\u4f18\u7684\u503c\uff0c\u6240\u4ee5\u8fd9\u4e2a\u60c5\u51b5\u5e76\u4e0d\u9700\u8981\u8003\u8651\u5bf9best\u8fdb\u884c\u66f4\u65b0\uff0c\u53cd\u6b63\u5b83\u4e5f\u6210\u4e0d\u4e86\u6700\u4f18\u3002<\/p>\n

\u4ee3\u7801<\/h3>\n
class Solution {\npublic:\n    int characterReplacement(string s, int k) {\n        \/\/sliding window solution\n        int charCount[26] = {0};\n        int w_start = 0, best = 0;\n        for(int w_end = 0; w_end < s.size(); w_end++){\n            charCount[s[w_end]-'A']++;\n            best = max(best, charCount[s[w_end]-'A']);\n            if(best+k <= w_end-w_start){\n                \/\/replace k chars in current window,\n                \/\/ if we still can't have the optimal\n                \/\/ we will shrink the left border of window\n                charCount[s[w_start]-'A']--;\n                w_start++;\n            }\n        }\n        return s.size()-w_start;\n    }\n};<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u601d\u8def\u5f88\u91cd\u8981\u3002 \u7ed9\u5b9a\u4e00\u4e2a\u957f\u5ea6n\u7684\u5b57\u7b26\u4e32s\u548c\u9650\u5236k\uff0c\u5c06s\u4e2d\u7684\u90e8\u5206\u5b57\u7b26\u66ff\u6362(\u66ff\u6362\u6b21\u6570<=k)\u540e\uff0c\u80fd\u5f97\u5230\u8fde\u7eed\u5b57\u7b26\uff08\u5982AAAA\uff09\u7684\u957f\u5ea6\u6700\u5927\u4e3a\u591a\u5c11\uff1f \u4f7f\u7528\u6ed1\u52a8\u7a97\u53e3\u7684\u601d\u8def\u53ef\u4ee5\u5728O(n)\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u60c5\u51b5\u4e0b\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u3002\u9700\u8981\u8bb0\u5f55\u5f53\u524d\u7a97\u53e3\u5185\u5404\u4e2a\u5b57\u7b26\u7684\u8ba1\u6570\u503c\uff08\u53ef\u4ee5\u770b\u505a\u5206\u5e03\u60c5\u51b5\uff09\u4ee5\u53ca\u5f53\u524d\u7a97\u53e3\u7684\u8d77\u59cb\u70b9\uff0c\u7a97\u53e3\u5185\u6700\u591a\u5b57\u7b26\u7684\u8ba1\u6570best\u3002\u6211\u4eec\u77e5\u9053\uff0c\u6700\u591a\u5b57\u7b26\u7684\u8ba1\u6570best+\u4fee\u6539\u6570\u91cfk\u5982\u679c\u8fd8\u662f\u4e0d\u80fd\u4f7f\u5f97\u5f53\u524d\u7a97\u53e3\u5185\u7684\u5b57\u7b26\u90fd\u7edf\u4e00\u7684\u8bdd\uff0c\u5c31\u5f97\u628a\u7a97\u53e3\u7f29\u5c0f\uff08\u8d77\u59cb\u70b9\u540e\u632a\uff09\u3002\u7a97\u53e3\u7f29\u5c0f\u65f6\u8bb0\u5f97\u628a\u7a97\u53e3\u8ba1\u6570\u66f4\u65b0\u4e00\u4e0b\u3002 \u8fd9\u91cc\u6709\u4e00\u4e2atricky\u7684\u5730\u65b9\uff0cbest\u503c\u672c\u6765\u5728\u6ed1\u52a8\u7a97\u53e3\u7684\u65f6\u5019\u662f\u8981\u66f4\u65b0\u7684\uff0c\u56e0\u4e3a\u53ef\u80fd\u7a97\u53e3\u8fc7\u4e86\u8fd9\u4e2abest\u4f1a\u53d8\u5c0f\u3002\u4f46\u662f\u7531\u4e8e\u6211\u4eec\u8981\u627e\u7684\u53ea\u662f\u4e2a\u6700\u4f18\u7684\u503c\uff0c\u6240\u4ee5\u8fd9\u4e2a\u60c5\u51b5\u5e76\u4e0d\u9700\u8981\u8003\u8651\u5bf9best\u8fdb\u884c\u66f4\u65b0\uff0c\u53cd\u6b63\u5b83\u4e5f\u6210\u4e0d\u4e86\u6700\u4f18\u3002 \u4ee3\u7801 class Solution { public: int characterReplacement(string s, int k) { \/\/sliding window solution int charCount[26] = {0}; int w_start = 0, best = 0; for(int w_end = 0; w_end < s.size(); w_end++){ charCount[s[w_end]-‘A’]++; best = max(best, charCount[s[w_end]-‘A’]); if(best+k <= w_end-w_start){ \/\/replace k chars in current window, \/\/ if we still […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-2308","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2308","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2308"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2308\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2308"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2308"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2308"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}