In a string\u00a0 For example, a string like\u00a0 Call a group\u00a0large<\/em>\u00a0if it has 3 or more characters.\u00a0 We would like the starting and ending positions of every large group.<\/p>\n The final answer should be in lexicographic order.<\/p>\n Example 1:<\/strong><\/p>\n Example 2:<\/strong><\/p>\n Example 3:<\/strong><\/p>\n <\/p>\n Note:\u00a0<\/strong>\u00a0 Time complexity: O(n)<\/p>\n Space complexity: O(n)<\/p>\n C++<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" Problem In a string\u00a0S\u00a0of lowercase letters, these letters form consecutive groups of the same character. For example, a string like\u00a0S = “abbxxxxzyy”\u00a0has the groups\u00a0“a”,\u00a0“bb”,\u00a0“xxxx”,\u00a0“z”\u00a0and\u00a0“yy”. Call…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,47],"tags":[288,222,4],"class_list":["post-2832","post","type-post","status-publish","format-standard","hentry","category-array","category-string","tag-count","tag-easy","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2832","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2832"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2832\/revisions"}],"predecessor-version":[{"id":2834,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2832\/revisions\/2834"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2832"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2832"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2832"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}S<\/code>\u00a0of lowercase letters, these letters form consecutive groups of the same character.<\/p>\nS = \"abbxxxxzyy\"<\/code>\u00a0has the groups\u00a0\"a\"<\/code>,\u00a0\"bb\"<\/code>,\u00a0\"xxxx\"<\/code>,\u00a0\"z\"<\/code>\u00a0and\u00a0\"yy\"<\/code>.<\/p>\nInput: <\/strong>\"abbxxxxzzy\"\r\nOutput: <\/strong>[[3,6]]\r\nExplanation<\/strong>:
\"xxxx\" is the single <\/code>large group with starting 3 and ending positions 6.<\/pre>\nInput: <\/strong>\"abc\"\r\nOutput: <\/strong>[]\r\nExplanation<\/strong>: We have \"a\",\"b\" and \"c\" but no large group.\r\n<\/pre>\n
Input: <\/strong>\"abcdddeeeeaabbbcd\"\r\nOutput: <\/strong>[[3,5],[6,9],[12,14]]<\/pre>\n
1 <= S.length <= 1000<\/code><\/p>\nSolution: Brute Force<\/strong><\/h1>\n
\/\/ Author: Huahua\r\n\/\/ Running time: 18 ms\r\nclass Solution {\r\npublic:\r\n vector<vector<int>> largeGroupPositions(string S) {\r\n constexpr int kLargeGroupSize = 3;\r\n const int n = S.size();\r\n vector<vector<int>> ans;\r\n int c = 0;\r\n for (int i = 0; i <= n; ++i, ++c) {\r\n if (i == n || S[i] != S[i - 1]) {\r\n if (c >= kLargeGroupSize) ans.push_back({i - c, i - 1});\r\n c = 0;\r\n }\r\n }\r\n return ans;\r\n }\r\n};<\/pre>\n