{"id":920,"date":"2025-08-20T12:58:31","date_gmt":"2025-08-20T07:28:31","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=920"},"modified":"2025-08-20T12:58:32","modified_gmt":"2025-08-20T07:28:32","slug":"longest-repeating-character-replacement","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/","title":{"rendered":"Longest Repeating Character Replacement | Leetcode 424"},"content":{"rendered":"\n<p>The problem&nbsp;<strong>\u201cLongest Repeating Character Replacement\u201d<\/strong>&nbsp;asks for the length of the longest substring that can be converted into a string of all the same character by replacing at most&nbsp;<strong>k<\/strong>&nbsp;characters. In other words, within any window, if the number of characters that are not the most frequent character is \u2264&nbsp;<strong>k<\/strong>, that window is valid.<\/p>\n\n\n\n<p>This is a hallmark&nbsp;<strong>sliding window<\/strong>&nbsp;problem where the key insight is to track the&nbsp;<strong>most frequent character count<\/strong>&nbsp;in the current window, and ensure the window size minus this count is within the replacement budget&nbsp;<strong>k<\/strong>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/longest-repeating-character-replacement\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>You are given a string&nbsp;<code>s<\/code>&nbsp;and an integer&nbsp;<code>k<\/code>. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most&nbsp;<code>k<\/code>&nbsp;times.<\/p>\n\n\n\n<p>Return&nbsp;<em>the length of the longest substring containing the same letter you can get after performing the above operations<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> s = \"ABAB\", k = 2\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> Replace the two 'A's with two 'B's or vice versa.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> s = \"AABABBA\", k = 1\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> Replace the one 'A' in the middle with 'B' and form \"AABBBBA\".\nThe substring \"BBBB\" has the longest repeating letters, which is 4.\nThere may exists other ways to achieve this answer too.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;= s.length &lt;= 10<sup>5<\/sup><\/code><\/li>\n\n\n\n<li><code>s<\/code>\u00a0consists of only uppercase English letters.<\/li>\n\n\n\n<li><code>0 &lt;= k &lt;= s.length<\/code><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-59f17594-bde7-464a-83ed-3eb9474868e8\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#0-brute-force-check-all-starts-grow-while-valid\" style=\"\">Brute Force (Check All Starts, Grow While Valid)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#1-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#2-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#3-why-it-works\" style=\"\">Why It Works<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#4-complexity\" style=\"\">Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#5-better-sliding-window-with-recompute-of-max_freq-inside-shrink-loop\" style=\"\">Better (Sliding Window with Recompute of max_freq Inside Shrink Loop)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#6-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#7-code-\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#8-why-it-works\" style=\"\">Why It Works<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#9-complexity\" style=\"\">Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#10-optimal-sliding-window-with-monotone-max_freq-tracking\" style=\"\">Optimal (Sliding Window with Monotone max_freq Tracking)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#11-intuition-and-approach\" style=\"\">Intuition and Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#12-code-\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#13-why-this-is-correct-and-optimal-\" style=\"\">Why This Is Correct and\u00a0Optimal<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#14-complexity\" style=\"\">Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#15-deep-dive-the-key-invariant\" style=\"\">Deep Dive: The Key Invariant<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#16-common-pitfalls-and-pro-tips-\" style=\"\">Common\u00a0Pitfalls\u00a0and\u00a0Pro Tips<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#17-when-to-choose-which\" style=\"\">When to Choose Which<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/longest-repeating-character-replacement\/#18-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-brute-force-check-all-starts-grow-while-valid\">Brute Force (Check All Starts, Grow While Valid)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>For each start index\u00a0<code>i<\/code>, expand\u00a0<code>j<\/code>\u00a0and maintain a\u00a0<strong>frequency map<\/strong>\u00a0plus the\u00a0<strong>max frequency<\/strong>\u00a0in the current window.<\/li>\n\n\n\n<li>Compute the replacements needed:\u00a0<code>changes = (j - i + 1) - max_freq<\/code>.<\/li>\n\n\n\n<li>If\u00a0<code>changes \u2264 k<\/code>, it\u2019s valid; update answer; otherwise break (further expansion only increases changes).<\/li>\n<\/ul>\n\n\n\n<p>This approach is intuitive and clean but remains&nbsp;<strong>O(n^2)<\/strong>&nbsp;in the worst case because for each&nbsp;<code>i<\/code>, we may scan many&nbsp;<code>j<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def characterReplacement(self, s: str, k: int) -&gt; int:\n        max_length = 0\n        n = len(s)\n        for i in range(0, n):\n            hash_map = dict()\n            max_freq = 0\n            for j in range(i, n):\n                hash_map[s[j]] = hash_map.get(s[j], 0) + 1\n                max_freq = max(max_freq, hash_map[s[j]])\n                changes = (j - i + 1) - max_freq\n                if changes &lt;= k:\n                    max_length = max(max_length, j - i + 1)\n                else:\n                    break\n        return max_length\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">characterReplacement<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">s<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">k<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        max_length = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(s)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            hash_map = <\/span><span style=\"color: #4EC9B0\">dict<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            max_freq = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(i, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                hash_map[s[j]] = hash_map.get(s[j], <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">) + <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                max_freq = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_freq, hash_map[s[j]])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                changes = (j - i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">) - max_freq<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> changes &lt;= k:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    max_length = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_length, j - i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">else<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">break<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> max_length<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-why-it-works\">Why It Works<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The\u00a0<strong>max_freq<\/strong>\u00a0character is treated as the \u201ctarget\u201d character to keep; the rest must be replaced.<\/li>\n\n\n\n<li>As soon as replacements exceed\u00a0<strong>k<\/strong>, expanding further cannot help (window only grows), so break.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-complexity\">Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>\u00a0O(n^2)<\/li>\n\n\n\n<li><strong>Space:<\/strong>\u00a0O(\u03a3) for frequency map (\u03a3 is alphabet size, typically 26 for uppercase letters)<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"5-better-sliding-window-with-recompute-of-max_freq-inside-shrink-loop\">Better (Sliding Window with Recompute of max_freq Inside Shrink Loop)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Use a classic\u00a0<strong>sliding window<\/strong>\u00a0with two pointers (<code>left<\/code>,\u00a0<code>right<\/code>).<\/li>\n\n\n\n<li>Expand\u00a0<code>right<\/code>, update frequency map, and track\u00a0<strong>max_freq<\/strong>.<\/li>\n\n\n\n<li>If the window becomes invalid (<code>window_size - max_freq > k<\/code>),\u00a0<strong>shrink<\/strong>\u00a0from the left.<\/li>\n\n\n\n<li>This version recomputes\u00a0<strong>max_freq<\/strong>\u00a0by scanning the frequency map during shrink, which is acceptable since \u03a3 is small (e.g., uppercase A\u2013Z).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-code-\">Code <\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def characterReplacement(self, s: str, k: int) -&gt; int:\n        max_length = 0\n        n = len(s)\n        left = 0\n        right = 0\n        hash_map = dict()\n        max_freq = 0\n        while right &lt; n:\n            hash_map[s[right]] = hash_map.get(s[right], 0) + 1\n            max_freq = max(max_freq, hash_map[s[right]])\n            while right - left + 1 - max_freq &gt; k:\n                hash_map[s[left]] -= 1\n                max_freq = 0\n                for v in hash_map.values():\n                    max_freq = max(max_freq, v)\n                left += 1\n\n            max_length = max(max_length, right - left + 1)\n            right += 1\n        return max_length\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">characterReplacement<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">s<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">k<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        max_length = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(s)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        right = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        hash_map = <\/span><span style=\"color: #4EC9B0\">dict<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        max_freq = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> right &lt; n:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            hash_map[s[right]] = hash_map.get(s[right], <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">) + <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            max_freq = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_freq, hash_map[s[right]])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> right - left + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> - max_freq &gt; k:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                hash_map[s[left]] -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                max_freq = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> v <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> hash_map.values():<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    max_freq = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_freq, v)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                left += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            max_length = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_length, right - left + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            right += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> max_length<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-why-it-works\">Why It Works<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The window is always adjusted to satisfy the\u00a0<strong>validity<\/strong>\u00a0criterion.<\/li>\n\n\n\n<li>Recomputing\u00a0<code>max_freq<\/code>\u00a0in the shrink loop keeps correctness even if the most frequent character count drops due to\u00a0<code>left<\/code>\u00a0moving.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-complexity\">Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>\u00a0O(26\u00b7n) \u2248\u00a0<strong>O(n)<\/strong>\u00a0for uppercase English letters (or\u00a0<strong>O(\u03a3\u00b7n)<\/strong>\u00a0in general)<\/li>\n\n\n\n<li><strong>Space:<\/strong>\u00a0O(\u03a3)<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"10-optimal-sliding-window-with-monotone-max_freq-tracking\">Optimal (Sliding Window with Monotone max_freq Tracking)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-intuition-and-approach\">Intuition and Approach<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Same sliding window, but we keep\u00a0<strong>max_freq<\/strong>\u00a0as a non-decreasing value as\u00a0<code>right<\/code>\u00a0expands.<\/li>\n\n\n\n<li>When shrinking from the left, we do NOT forcibly decrease\u00a0<code>max_freq<\/code>. This is safe and a well-known trick: even if\u00a0<code>max_freq<\/code>\u00a0is slightly larger than the true current window max, the condition\u00a0<code>right - left + 1 - max_freq > k<\/code>\u00a0remains a correct filter (we might keep the window slightly larger, but we never overcount because we only use the condition to force shrinking, not to extend beyond validity).<\/li>\n\n\n\n<li>This ensures fully\u00a0<strong>linear<\/strong>\u00a0time with no recomputation.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-\">Code <\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.5rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def characterReplacement(self, s: str, k: int) -&gt; int:\n        max_length = 0\n        n = len(s)\n        left = 0\n        right = 0\n        hash_map = dict()\n        max_freq = 0\n        while right &lt; n:\n            hash_map[s[right]] = hash_map.get(s[right], 0) + 1\n            max_freq = max(max_freq, hash_map[s[right]])\n            while right - left + 1 - max_freq &gt; k:\n                hash_map[s[left]] -= 1\n                left += 1\n\n            max_length = max(max_length, right - left + 1)\n            right += 1\n        return max_length\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">characterReplacement<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">s<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">str<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">k<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        max_length = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(s)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        left = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        right = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        hash_map = <\/span><span style=\"color: #4EC9B0\">dict<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        max_freq = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> right &lt; n:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            hash_map[s[right]] = hash_map.get(s[right], <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">) + <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            max_freq = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_freq, hash_map[s[right]])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> right - left + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\"> - max_freq &gt; k:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                hash_map[s[left]] -= <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                left += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            max_length = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_length, right - left + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            right += <\/span><span style=\"color: #B5CEA8\">1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> max_length<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-why-this-is-correct-and-optimal-\">Why This Is Correct and&nbsp;<strong>Optimal<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The window condition relies on\u00a0<code>max_freq<\/code>\u00a0being an upper bound of the true max frequency in the window.<\/li>\n\n\n\n<li>Not reducing\u00a0<code>max_freq<\/code>\u00a0during shrink does not cause false acceptance; at worst, it causes extra shrinking later when needed.<\/li>\n\n\n\n<li>Each index moves at most once for\u00a0<code>right<\/code>\u00a0and at most once for\u00a0<code>left<\/code>, ensuring\u00a0<strong>O(n)<\/strong>\u00a0time.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-complexity\">Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time:<\/strong>\u00a0<strong>O(n)<\/strong><\/li>\n\n\n\n<li><strong>Space:<\/strong>\u00a0<strong>O(\u03a3)<\/strong><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"15-deep-dive-the-key-invariant\">Deep Dive: The Key Invariant<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Let\u00a0<code>window_size = right - left + 1<\/code>\u00a0and\u00a0<code>max_freq = max count of any char in window<\/code>.<\/li>\n\n\n\n<li>The number of replacements needed to make the window all the same char is\u00a0<code>window_size - max_freq<\/code>.<\/li>\n\n\n\n<li>A window is\u00a0<strong>valid<\/strong>\u00a0iff\u00a0<code>window_size - max_freq \u2264 k<\/code>.<\/li>\n\n\n\n<li>The algorithm keeps the window\u00a0<strong>maximal<\/strong>\u00a0subject to this constraint; hence the longest seen window is the answer.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-common-pitfalls-and-pro-tips-\">Common&nbsp;<strong>Pitfalls<\/strong>&nbsp;and&nbsp;<strong>Pro Tips<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Always compute\u00a0<code>changes = window_size - max_freq<\/code>. If this exceeds\u00a0<strong>k<\/strong>,\u00a0<strong>shrink<\/strong>.<\/li>\n\n\n\n<li>In the\u00a0<strong>optimal<\/strong>\u00a0version, do not try to decrease\u00a0<code>max_freq<\/code>\u00a0during shrink; this can degrade performance without improving correctness.<\/li>\n\n\n\n<li>If the alphabet is known and small (e.g., uppercase), using a\u00a0<strong>fixed-size array<\/strong>\u00a0(size 26) instead of a dictionary is a micro-optimization.<\/li>\n\n\n\n<li>Works for any alphabet; just remember\u00a0<strong>\u03a3<\/strong>\u00a0impacts memory and the constants if you recompute.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"17-when-to-choose-which\">When to Choose Which<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Use the\u00a0<strong>Brute Force<\/strong>\u00a0version only for learning or very small inputs.<\/li>\n\n\n\n<li>Use the\u00a0<strong>Better<\/strong>\u00a0version if recomputing\u00a0<code>max_freq<\/code>\u00a0is simpler for you and \u03a3 is small &#8211; still effectively linear.<\/li>\n\n\n\n<li>Use the\u00a0<strong>Optimal<\/strong>\u00a0version for the cleanest\u00a0<strong>O(n)<\/strong>\u00a0performance without recomputation.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"18-summary\">Summary<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Core idea: In any window, the minimum changes to make it uniform equals\u00a0<code>window_size - max_freq<\/code>.<\/li>\n\n\n\n<li>Maintain a sliding window, track frequencies, and ensure\u00a0<code>window_size - max_freq \u2264 k<\/code>.<\/li>\n\n\n\n<li>The\u00a0<strong>optimal<\/strong>\u00a0approach with a non-decreasing\u00a0<code>max_freq<\/code>\u00a0achieves\u00a0<strong>O(n)<\/strong>\u00a0time and\u00a0<strong>O(\u03a3)<\/strong>\u00a0space &#8211; ideal for interviews and production.<\/li>\n<\/ul>\n\n\n\n<p>This pattern, max window with a bounded number of changes based on the dominant character is extremely powerful and reappears in various\u00a0<strong>string sliding window<\/strong>\u00a0problems.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The problem&nbsp;\u201cLongest Repeating Character Replacement\u201d&nbsp;asks for the length of the longest substring that can be converted into a string of all the same character by replacing at most&nbsp;k&nbsp;characters. In other words, within any window, if the number of characters that are not the most frequent character is \u2264&nbsp;k, that window is valid. This is a<\/p>\n","protected":false},"author":1,"featured_media":922,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[19,40],"class_list":{"0":"post-920","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-medium","10":"tag-sliding-window-and-two-pointers"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/08\/longest-repeating-character-replacement-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/920","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=920"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/920\/revisions"}],"predecessor-version":[{"id":923,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/920\/revisions\/923"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/922"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=920"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=920"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=920"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}