{"id":1660,"date":"2024-02-06T18:00:00","date_gmt":"2024-02-06T18:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1660"},"modified":"2024-02-08T11:19:38","modified_gmt":"2024-02-08T11:19:38","slug":"longest-repeating-character-replacement","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/longest-repeating-character-replacement\/","title":{"rendered":"Longest Repeating Character Replacement Problem"},"content":{"rendered":"\n<p>There are a lot of programming problems related to strings of different difficulty levels. In this article, we will discuss the Longest Repeating Character Replacement problem from leetcode which falls under the concept of string manipulation. We will also implement it in C++, Java, and Python.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Longest Repeating Character Replacement<\/strong><\/h2>\n\n\n\n<p><strong>In this Longest Repeating Character Replacement problem, we are given a string and an integer we can choose any character of the string and change it to any other uppercase English character. We can perform this operation at most k times. We have to perform the above operation in such a way that we can get the length of the longest substring.<\/strong><\/p>\n\n\n\n<p>Let us discuss this better with an example:<\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color wp-elements-dc82c8bf9b8ca07088432c520e917c1f\" style=\"background-color:#fedcba\"><code><strong>Input: <\/strong>\ns = \"AABABBA\", k = 1\n\n<strong>Output: <\/strong>\n4<\/code><\/pre>\n\n\n\n<p>Here we can replace A at index 3 with B to get four consecutive B or we can replace B at index 2 with A to get four consecutive A.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solve using Sliding Window and HashMap<\/strong><\/h2>\n\n\n\n<p>In this approach, we will use the concept of a <a href=\"https:\/\/favtutor.com\/blogs\/sliding-window-algorithm\">sliding window<\/a> in which we use sliding window to expand and contract while maintaining the count of characters within the window.<\/p>\n\n\n\n<p>Below are the steps to be used in this approach:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>First of all, we will declare an unordered map to keep track of the count of each character present in the given string.<\/li>\n\n\n\n<li>Now we will initialize three variables \u201cans\u201d, \u201cleft\u201d, and \u201cright\u201d\n<ul class=\"wp-block-list\">\n<li>ans keeps track of the maximum length of the substring and left and right maintains window size.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Now we will iterate through our string using the right pointer and update our map with the frequency of characters. Simultaneously we will check if the length of the current substring minus the frequency of the most frequent character exceeds the allowed replacement \u201ck\u201d<\/li>\n\n\n\n<li>If yes then we will move the left pointer to the right and decrease the count of the character at the left.<\/li>\n\n\n\n<li>If not then we will update our ans with maximum window size.<\/li>\n\n\n\n<li>At last, we will return our ans after we iterate our string.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Below is the solution for longest repeating character replacement:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;iostream&gt;\n#include &lt;unordered_map&gt;\n#include &lt;algorithm&gt;\n\nusing namespace std;\n\nint characterReplacement(const string&amp; s, int k) {\n    \/\/ Initialize an unordered_map to keep track of the count of each character\n    unordered_map&lt;char, int&gt; alphabets;\n\n    \/\/ Initialize variables for the answer and left pointer\n    int ans = 0;\n    int left = 0;\n\n    \/\/ Iterate through the string using the right pointer\n    for (int right = 0; right &lt; s.length(); ++right) {\n        \/\/ Update the count of the current character in the unordered_map\n        alphabets[s[right]] = 1 + alphabets[s[right]];\n\n        \/\/ Check if the current window size minus the count of the most frequent character\n        \/\/ is greater than the allowed replacements (k)\n        if ((right - left + 1) - max_element(alphabets.begin(), alphabets.end(),\n            [](const auto&amp; p1, const auto&amp; p2) { return p1.second &lt; p2.second; })-&gt;second &gt; k) {\n            \/\/ If so, move the left pointer and decrease the count of the character at the left\n            alphabets[s[left]] -= 1;\n            left += 1;\n        } \n      \telse {\n            \/\/ Update the answer with the maximum window size\n            ans = max(ans, (right - left + 1));\n        }\n    }\n\n    \/\/ Return the final answer\n    return ans;\n}\n\nint main() {\n    string s = &quot;AABABBA&quot;;\n    int k = 1;\n\n    int result = characterReplacement(s, k);\n\n    cout &lt;&lt; &quot;Result: &quot; &lt;&lt; result &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Implement the solution for the longest repeating character replacement:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def character_replacement(s, k):\n    # Initialize a dictionary to keep track of the count of each character\n    alphabets = {}\n    # Initialize variables for the answer and left pointer\n    ans = 0\n    left = 0\n\n    # Iterate through the string using the right pointer\n    for right in range(len(s)):\n        # Update the count of the current character in the dictionary\n        alphabets[s[right]] = 1 + alphabets.get(s[right], 0)\n\n        # Check if the current window size minus the count of the most frequent character\n        # is greater than the allowed replacements (k)\n        if (right - left + 1) - max(alphabets.values()) &gt; k:\n            # If so, move the left pointer and decrease the count of the character at the left\n            alphabets[s[left]] -= 1\n            left += 1\n        else:\n            # Update the answer with the maximum window size\n            ans = max(ans, (right - left + 1))\n\n    return ans\n\n# Example usage\ns = &quot;AABABBA&quot;\nk = 1\nresult = character_replacement(s, k)\nprint(&quot;Result:&quot;, result)<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Implement it in Java also:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.HashMap;\nimport java.util.Map;\n\npublic class CharacterReplacement {\n    public static int characterReplacement(String s, int k) {\n        \/\/ Initialize a map to keep track of the count of each character\n        Map&lt;Character, Integer&gt; alphabets = new HashMap&lt;&gt;();\n        \/\/ Initialize variables for the answer and left pointer\n        int ans = 0;\n        int left = 0;\n\n        \/\/ Iterate through the string using the right pointer\n        for (int right = 0; right &lt; s.length(); ++right) {\n            \/\/ Update the count of the current character in the map\n            alphabets.put(s.charAt(right), 1 + alphabets.getOrDefault(s.charAt(right), 0));\n\n            \/\/ Check if the current window size minus the count of the most frequent character\n            \/\/ is greater than the allowed replacements (k)\n            if ((right - left + 1) - alphabets.values().stream().max(Integer::compare).orElse(0) &gt; k) {\n                \/\/ If so, move the left pointer and decrease the count of the character at the left\n                alphabets.put(s.charAt(left), alphabets.get(s.charAt(left)) - 1);\n                left += 1;\n            } \n          \telse {\n                \/\/ Update the answer with the maximum window size\n                ans = Math.max(ans, (right - left + 1));\n            }\n        }\n\n        return ans;\n    }\n\n    public static void main(String[] args) {\n        \/\/ Example usage\n        String s = &quot;AABABBA&quot;;\n        int k = 1;\n        int result = characterReplacement(s, k);\n        System.out.println(&quot;Result: &quot; + result);\n    }\n}<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color wp-elements-e90c7b41d689fb8c985c1ed9d0a1cef4\" style=\"background-color:#fedcba\"><code>Result: 4<\/code><\/pre>\n\n\n\n<p>The Time Complexity to solve the longest repeating character replacement problem using sliding window and hashmap is O(N) where n is the length of the string because our left and right pointers traverse the string exactly once.<\/p>\n\n\n\n<p>The Space Complexity is O(1) because the hashmap can have a maximum of 26 unique characters and the size of the hashmap will remain constant.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, we found that the sliding window approach provides an efficient solution for the longest repeating character replacement <a href=\"https:\/\/leetcode.com\/problems\/longest-repeating-character-replacement\/description\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> with time complexity of O(N) and space complexity of O(1) we have also implemented code in C++, Java, and Python.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Understand the Longest Repeating Character Replacement problem from leetcode and solve it using the sliding window and hashing approach.<\/p>\n","protected":false},"author":12,"featured_media":1662,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1660","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1660","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1660"}],"version-history":[{"count":4,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1660\/revisions"}],"predecessor-version":[{"id":1694,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1660\/revisions\/1694"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1662"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1660"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1660"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1660"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}