{"id":34246,"date":"2024-11-01T09:25:58","date_gmt":"2024-11-01T09:25:58","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34246"},"modified":"2024-11-01T10:58:00","modified_gmt":"2024-11-01T10:58:00","slug":"c-coding-test-course-sliding-window-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34246\/","title":{"rendered":"C++ Coding Test Course, Sliding Window"},"content":{"rendered":"<div class=\"blog-post\">\n<h2>C++ Coding Test Course: Sliding Window<\/h2>\n<p>\n        Welcome! In this course, we will explore the popular algorithm technique known as <strong>Sliding Window<\/strong>.<br \/>\n        The sliding window technique is frequently used when processing subsequences or subarrays in one-dimensional data structures such as arrays or strings.<br \/>\n        It can greatly help in efficiently reducing complexity and solving problems.<br \/>\n        In this post, we will explain the concept of sliding window and solve specific algorithm problems using it.\n    <\/p>\n<h3>What is Sliding Window?<\/h3>\n<p>\n        The sliding window technique involves setting a window of fixed size on an array or string and then moving that window from left to right during the exploration.<br \/>\n        This technique efficiently navigates or calculates elements within the array, generally providing a significant advantage in reducing time complexity.<br \/>\n        Sliding window can be broadly divided into two types:\n    <\/p>\n<ul>\n<li><strong>Fixed Size Window<\/strong>: When the size of the window is fixed. For example, a problem that calculates the sum of K consecutive elements.<\/li>\n<li><strong>Variable Size Window<\/strong>: When the size of the window is variable. For example, a problem that finds the shortest subarray that satisfies a certain condition.<\/li>\n<\/ul>\n<h3>Problem Description: Longest Substring<\/h3>\n<p>\n        The problem we will solve this time is as follows:<br \/>\n        Find the length of the longest substring without repeating characters from a given string.<br \/>\n        For example, when the input string is <code>\"abcabcbb\"<\/code>, the output will be <strong>3<\/strong>. (The longest substring is <code>\"abc\"<\/code>.)\n    <\/p>\n<h3>Approach to Solve the Problem<\/h3>\n<p>\n        The sliding window is a suitable strategy for effectively solving this problem.<br \/>\n        Here, we will use two pointers to check if there are any duplicate characters in the current window, and adjust the size of the window from both sides.<br \/>\n        The main variables to be used in this approach are as follows:\n    <\/p>\n<ul>\n<li><strong>left<\/strong>: The starting index of the window<\/li>\n<li><strong>right<\/strong>: The ending index of the window<\/li>\n<li><strong>max_length<\/strong>: The length of the longest substring<\/li>\n<li><strong>char_set<\/strong>: A set to store the characters in the current window<\/li>\n<\/ul>\n<h3>Algorithm Steps<\/h3>\n<ol>\n<li>Initialize the left pointer <code>left<\/code> and the right pointer <code>right<\/code> to 0.<\/li>\n<li>Initialize the character set <code>char_set<\/code>.<\/li>\n<li>Move the right pointer <code>right<\/code> to the end of the string while performing the following:<\/li>\n<ul>\n<li>If <code>char_set<\/code> already contains <code>s[right]<\/code>, a duplicate has occurred, so increment the left pointer <code>left<\/code> to remove the duplicate.<\/li>\n<li>If there are no duplicates, add <code>s[right]<\/code> to <code>char_set<\/code>.<\/li>\n<li>Calculate the current window length <code>right - left + 1<\/code> and compare it with <code>max_length<\/code>, updating it accordingly.<\/li>\n<li>Increment the right pointer <code>right<\/code>.<\/li>\n<\/ul>\n<li>After exploring the entire string, return <code>max_length<\/code>.<\/li>\n<\/ol>\n<h3>C++ Code Implementation<\/h3>\n<pre><code class=\"language-cpp\">\n#include &lt;iostream&gt;\n#include &lt;unordered_set&gt;\n#include &lt;string&gt;\n\nusing namespace std;\n\nint lengthOfLongestSubstring(string s) {\n    unordered_set<char> char_set; \/\/ Character set of the current window\n    int left = 0, max_length = 0;\n\n    for (int right = 0; right &lt; s.length(); ++right) {\n        \/\/ Move the left pointer until no duplicate characters occur\n        while (char_set.find(s[right]) != char_set.end()) {\n            char_set.erase(s[left]);\n            ++left;\n        }\n        \/\/ Add the current character\n        char_set.insert(s[right]);\n        \/\/ Update maximum length\n        max_length = max(max_length, right - left + 1);\n    }\n    return max_length;\n}\n\nint main() {\n    string s = \"abcabcbb\";\n    cout &lt;&lt; \"Length of the longest substring: \" &lt;&lt; lengthOfLongestSubstring(s) &lt;&lt; endl;\n    return 0;\n}\n<\/code><\/pre>\n<h3>Code Explanation<\/h3>\n<p>\n        In the above code, we use <code>unordered_set<\/code> to store the characters in the current window, and when a duplicate character occurs,<br \/>\n        we move the left pointer to remove the duplicate. Each time we process a character, we update the maximum length.<br \/>\n        This algorithm has a time complexity of O(n) when the length of the string is n.<br \/>\n        This is because both pointers only pass through the string once.<br \/>\n        The space complexity is O(min(n, m)), where n is the length of the string and m is the size of the character set.\n    <\/p>\n<h3>Conclusion<\/h3>\n<p>\n        In this post, we explored the process of solving the longest substring problem using the sliding window technique.<br \/>\n        The sliding window is a powerful tool that can efficiently solve many problems, and it allows for a more effective approach to tackle algorithmic challenges.<br \/>\n        In the next post, we will cover more algorithmic techniques and problems.<br \/>\n        I hope this helps you in your coding test preparation!\n    <\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>C++ Coding Test Course: Sliding Window Welcome! In this course, we will explore the popular algorithm technique known as Sliding Window. The sliding window technique is frequently used when processing subsequences or subarrays in one-dimensional data structures such as arrays or strings. It can greatly help in efficiently reducing complexity and solving problems. In this &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34246\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;C++ Coding Test Course, Sliding Window&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[111],"tags":[],"class_list":["post-34246","post","type-post","status-publish","format-standard","hentry","category-c-coding-test-tutorials-2"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>C++ Coding Test Course, Sliding Window - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/34246\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"C++ Coding Test Course, Sliding Window - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"C++ Coding Test Course: Sliding Window Welcome! In this course, we will explore the popular algorithm technique known as Sliding Window. The sliding window technique is frequently used when processing subsequences or subarrays in one-dimensional data structures such as arrays or strings. It can greatly help in efficiently reducing complexity and solving problems. In this &hellip; \ub354 \ubcf4\uae30 &quot;C++ Coding Test Course, Sliding Window&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34246\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:25:58+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T10:58:00+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34246\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34246\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"C++ Coding Test Course, Sliding Window\",\"datePublished\":\"2024-11-01T09:25:58+00:00\",\"dateModified\":\"2024-11-01T10:58:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34246\/\"},\"wordCount\":557,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"C++ Coding Test Tutorials\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34246\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34246\/\",\"name\":\"C++ Coding Test Course, Sliding Window - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:25:58+00:00\",\"dateModified\":\"2024-11-01T10:58:00+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34246\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34246\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34246\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"C++ Coding Test Course, Sliding Window\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"C++ Coding Test Course, Sliding Window - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/34246\/","og_locale":"ko_KR","og_type":"article","og_title":"C++ Coding Test Course, Sliding Window - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"C++ Coding Test Course: Sliding Window Welcome! In this course, we will explore the popular algorithm technique known as Sliding Window. The sliding window technique is frequently used when processing subsequences or subarrays in one-dimensional data structures such as arrays or strings. It can greatly help in efficiently reducing complexity and solving problems. In this &hellip; \ub354 \ubcf4\uae30 \"C++ Coding Test Course, Sliding Window\"","og_url":"https:\/\/atmokpo.com\/w\/34246\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:25:58+00:00","article_modified_time":"2024-11-01T10:58:00+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34246\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34246\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"C++ Coding Test Course, Sliding Window","datePublished":"2024-11-01T09:25:58+00:00","dateModified":"2024-11-01T10:58:00+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34246\/"},"wordCount":557,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["C++ Coding Test Tutorials"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34246\/","url":"https:\/\/atmokpo.com\/w\/34246\/","name":"C++ Coding Test Course, Sliding Window - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:25:58+00:00","dateModified":"2024-11-01T10:58:00+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34246\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34246\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34246\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"C++ Coding Test Course, Sliding Window"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34246","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=34246"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34246\/revisions"}],"predecessor-version":[{"id":34247,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34246\/revisions\/34247"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34246"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}