{"id":750,"date":"2022-05-08T12:13:43","date_gmt":"2022-05-08T04:13:43","guid":{"rendered":"https:\/\/tech.fredpan.cn\/conditional-substring-matching\/"},"modified":"2022-05-08T12:22:56","modified_gmt":"2022-05-08T04:22:56","slug":"conditional-substring-matching","status":"publish","type":"post","link":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/","title":{"rendered":"Conditional Substring Matching"},"content":{"rendered":"[vc_row type=”in_container” full_screen_row_position=”middle” column_margin=”default” column_direction=”default” column_direction_tablet=”default” column_direction_phone=”default” scene_position=”center” text_color=”dark” text_align=”left” row_border_radius=”none” row_border_radius_applies=”bg” overlay_strength=”0.3″ gradient_direction=”left_to_right” shape_divider_position=”bottom” bg_image_animation=”none”][vc_column column_padding=”no-extra-padding” column_padding_tablet=”inherit” column_padding_phone=”inherit” column_padding_position=”all” column_element_spacing=”default” background_color_opacity=”1″ background_hover_color_opacity=”1″ column_shadow=”none” column_border_radius=”none” column_link_target=”_self” gradient_direction=”left_to_right” overlay_strength=”0.3″ width=”1\/1″ tablet_width_inherit=”default” tablet_text_alignment=”default” phone_text_alignment=”default” bg_image_animation=”none” border_type=”simple” column_border_width=”none” column_border_style=”solid”][vc_column_text]Given m unique characters [a, b, c, d], and a string “tbcacbdata” of length n. Find a continuous substring s of “tbcacbdata” with length m, such that s only consists of all the characters in m, the order does not matter. Return any of the satisfied substring and the starting position of that substring, return -1 and an empty string if it is not found. For example, in the above example, one should return 3, “acbd”.<\/p>\n
package main\r\n\r\nimport \"fmt\"\r\n\r\nfunc main(){\r\n    printOutput(find([]byte{'a','b','d'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))\r\n\r\n    printOutput(find([]byte{'a','b','d', 'c'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))\r\n\r\n    printOutput(find([]byte{'t','b','c'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))\r\n\r\n    printOutput(find([]byte{'t'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))\r\n\r\n    printOutput(find([]byte{'c','b','a'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))\r\n\r\n    printOutput(find([]byte{'t','a'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))\r\n\r\n    printOutput(find([]byte{'g'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))\r\n}\r\n\r\nfunc find(a, b []byte) (int, string) {\r\n    mapping := map[byte]bool{}\r\n    \/\/ init\r\n    for _, n := range a {\r\n        mapping[n] = true\r\n    }\r\n    i := 0 \/\/ Sliding Window left\r\n    for j := 0; j < len(b); j++ { \/\/ Sliding Window right\r\n        v, ok := mapping[b[j]] \/\/ expand the window to the right\r\n        if ok && v{ \/\/ if current character is in m has not yet been used\r\n            \/\/ expand the window toward right untill reached the target size\r\n            mapping[b[j]] = false \/\/ mark as used\r\n            if j - i + 1 == len(a) { \/\/ exit condition: the window has the same size as m\r\n                return i, string(b[i: j + 1])\r\n            }\r\n        } else if ok && !v { \/\/ if current character is in m and has been used, such as \"cac\"\r\n            \/\/ update the left side of the winow: to the next of the position of the last appearance of current characters\r\n            if _, okk := mapping[b[i]]; okk {\r\n                for i <= j {\r\n                    if b[i] != b[j]  {\r\n                        mapping[b[i]] = true\r\n                        i++\r\n                    } else {\r\n                        break\r\n                    }\r\n                }\r\n                i++\r\n            }\r\n        } else { \/\/ if current character is NOT in m\r\n            \/\/ update the left side of the window to the position of window right, and mark everything bEFORE the window right as unused\r\n            for i <= j {\r\n                if _, okk := mapping[b[i]]; okk {\r\n                    mapping[b[i]] = true\r\n                }\r\n                i++\r\n            }\r\n        }\r\n    }\r\n    return -1, \"\"\r\n}\r\n\r\nfunc printOutput(pos int, str string){\r\n    if pos == -1 {\r\n        fmt.Printf(\"string not found\\n\")\r\n    } else {\r\n        fmt.Printf(\"start at pos: %d, string is: %s\\n\", pos, str)\r\n    }\r\n}<\/pre>\n[\/vc_column_text][\/vc_column][\/vc_row]\n","protected":false},"excerpt":{"rendered":"
[vc_row type=”in_container” full_screen_row_position=”middle” column_margin=”default” column_direction=”default” column_direction_tablet=”default” column_direction_phone=”default” scene_position=”center” text_color=”dark” text_align=”left” row_border_radius=”none” row_border_radius_applies=”bg” overlay_strength=”0.3″ gradient_direction=”left_to_right” shape_divider_position=”bottom” bg_image_animation=”none”][vc_column column_padding=”no-extra-padding” column_padding_tablet=”inherit” column_padding_phone=”inherit” column_padding_position=”all” column_element_spacing=”default” background_color_opacity=”1″ background_hover_color_opacity=”1″ column_shadow=”none” column_border_radius=”none” column_link_target=”_self” gradient_direction=”left_to_right” overlay_strength=”0.3″ width=”1\/1″ tablet_width_inherit=”default”…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[110],"tags":[],"yoast_head":"\nConditional Substring Matching - Tech Blog | Arctic Kingdom<\/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:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Conditional Substring Matching - Tech Blog | Arctic Kingdom\" \/>\n<meta property=\"og:description\" content=\"[vc_row type=”in_container” full_screen_row_position=”middle” column_margin=”default” column_direction=”default” column_direction_tablet=”default” column_direction_phone=”default” scene_position=”center” text_color=”dark” text_align=”left” row_border_radius=”none” row_border_radius_applies=”bg” overlay_strength=”0.3″ gradient_direction=”left_to_right” shape_divider_position=”bottom” bg_image_animation=”none”][vc_column column_padding=”no-extra-padding” column_padding_tablet=”inherit” column_padding_phone=”inherit” column_padding_position=”all” column_element_spacing=”default” background_color_opacity=”1″ background_hover_color_opacity=”1″ column_shadow=”none” column_border_radius=”none” column_link_target=”_self” gradient_direction=”left_to_right” overlay_strength=”0.3″ width=”1\/1″ tablet_width_inherit=”default”...\" \/>\n<meta property=\"og:url\" content=\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/\" \/>\n<meta property=\"og:site_name\" content=\"Tech Blog | Arctic Kingdom\" \/>\n<meta property=\"article:published_time\" content=\"2022-05-08T04:13:43+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-05-08T04:22:56+00:00\" \/>\n<meta name=\"author\" content=\"fredpan\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"fredpan\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/\"},\"author\":{\"name\":\"fredpan\",\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225\"},\"headline\":\"Conditional Substring Matching\",\"datePublished\":\"2022-05-08T04:13:43+00:00\",\"dateModified\":\"2022-05-08T04:22:56+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/\"},\"wordCount\":219,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225\"},\"articleSection\":[\"Algorithm\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/\",\"url\":\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/\",\"name\":\"Conditional Substring Matching - Tech Blog | Arctic Kingdom\",\"isPartOf\":{\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#website\"},\"datePublished\":\"2022-05-08T04:13:43+00:00\",\"dateModified\":\"2022-05-08T04:22:56+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/tech.fredpan.cn\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Conditional Substring Matching\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#website\",\"url\":\"https:\/\/tech.fredpan.cn\/en\/\",\"name\":\"Tech Blog | Arctic Kingdom\",\"description\":\"Liren Pan's Tech Blog. For sharing professional knowledge in Software Development Engineering, specialized in backend development.\",\"publisher\":{\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/tech.fredpan.cn\/en\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225\",\"name\":\"fredpan\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/tech.fredpan.cn\/wp-content\/uploads\/sites\/2\/2021\/06\/LirenPan-Avatar-Taken-in-UofT-Myhal-Building.jpg\",\"contentUrl\":\"https:\/\/tech.fredpan.cn\/wp-content\/uploads\/sites\/2\/2021\/06\/LirenPan-Avatar-Taken-in-UofT-Myhal-Building.jpg\",\"width\":690,\"height\":704,\"caption\":\"fredpan\"},\"logo\":{\"@id\":\"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/image\/\"},\"sameAs\":[\"http:\/\/129.226.182.46\"],\"url\":\"https:\/\/tech.fredpan.cn\/en\/author\/fredpan\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Conditional Substring Matching - Tech Blog | Arctic Kingdom","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:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/","og_locale":"en_US","og_type":"article","og_title":"Conditional Substring Matching - Tech Blog | Arctic Kingdom","og_description":"[vc_row type=”in_container” full_screen_row_position=”middle” column_margin=”default” column_direction=”default” column_direction_tablet=”default” column_direction_phone=”default” scene_position=”center” text_color=”dark” text_align=”left” row_border_radius=”none” row_border_radius_applies=”bg” overlay_strength=”0.3″ gradient_direction=”left_to_right” shape_divider_position=”bottom” bg_image_animation=”none”][vc_column column_padding=”no-extra-padding” column_padding_tablet=”inherit” column_padding_phone=”inherit” column_padding_position=”all” column_element_spacing=”default” background_color_opacity=”1″ background_hover_color_opacity=”1″ column_shadow=”none” column_border_radius=”none” column_link_target=”_self” gradient_direction=”left_to_right” overlay_strength=”0.3″ width=”1\/1″ tablet_width_inherit=”default”...","og_url":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/","og_site_name":"Tech Blog | Arctic Kingdom","article_published_time":"2022-05-08T04:13:43+00:00","article_modified_time":"2022-05-08T04:22:56+00:00","author":"fredpan","twitter_card":"summary_large_image","twitter_misc":{"Written by":"fredpan","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#article","isPartOf":{"@id":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/"},"author":{"name":"fredpan","@id":"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225"},"headline":"Conditional Substring Matching","datePublished":"2022-05-08T04:13:43+00:00","dateModified":"2022-05-08T04:22:56+00:00","mainEntityOfPage":{"@id":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/"},"wordCount":219,"commentCount":0,"publisher":{"@id":"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225"},"articleSection":["Algorithm"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/","url":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/","name":"Conditional Substring Matching - Tech Blog | Arctic Kingdom","isPartOf":{"@id":"https:\/\/tech.fredpan.cn\/en\/#website"},"datePublished":"2022-05-08T04:13:43+00:00","dateModified":"2022-05-08T04:22:56+00:00","breadcrumb":{"@id":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/tech.fredpan.cn\/en\/conditional-substring-matching\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/tech.fredpan.cn\/en\/"},{"@type":"ListItem","position":2,"name":"Conditional Substring Matching"}]},{"@type":"WebSite","@id":"https:\/\/tech.fredpan.cn\/en\/#website","url":"https:\/\/tech.fredpan.cn\/en\/","name":"Tech Blog | Arctic Kingdom","description":"Liren Pan's Tech Blog. For sharing professional knowledge in Software Development Engineering, specialized in backend development.","publisher":{"@id":"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/tech.fredpan.cn\/en\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/e895d0655e771d0e55a1644693ad4225","name":"fredpan","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/image\/","url":"https:\/\/tech.fredpan.cn\/wp-content\/uploads\/sites\/2\/2021\/06\/LirenPan-Avatar-Taken-in-UofT-Myhal-Building.jpg","contentUrl":"https:\/\/tech.fredpan.cn\/wp-content\/uploads\/sites\/2\/2021\/06\/LirenPan-Avatar-Taken-in-UofT-Myhal-Building.jpg","width":690,"height":704,"caption":"fredpan"},"logo":{"@id":"https:\/\/tech.fredpan.cn\/en\/#\/schema\/person\/image\/"},"sameAs":["http:\/\/129.226.182.46"],"url":"https:\/\/tech.fredpan.cn\/en\/author\/fredpan\/"}]}},"_links":{"self":[{"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/posts\/750"}],"collection":[{"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/comments?post=750"}],"version-history":[{"count":3,"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/posts\/750\/revisions"}],"predecessor-version":[{"id":753,"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/posts\/750\/revisions\/753"}],"wp:attachment":[{"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/media?parent=750"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/categories?post=750"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tech.fredpan.cn\/en\/wp-json\/wp\/v2\/tags?post=750"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}