{"id":9462,"date":"2022-02-04T16:21:58","date_gmt":"2022-02-05T00:21:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9462"},"modified":"2022-02-04T16:22:43","modified_gmt":"2022-02-05T00:22:43","slug":"leetcode-2147-number-of-ways-to-divide-a-long-corridor","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-2147-number-of-ways-to-divide-a-long-corridor\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2147. Number of Ways to Divide a Long Corridor"},"content":{"rendered":"\n

Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed<\/strong> string corridor<\/code> of length n<\/code> consisting of letters 'S'<\/code> and 'P'<\/code> where each 'S'<\/code> represents a seat and each 'P'<\/code> represents a plant.<\/p>\n\n\n\n

One room divider has already<\/strong> been installed to the left of index 0<\/code>, and another<\/strong> to the right of index n - 1<\/code>. Additional room dividers can be installed. For each position between indices i - 1<\/code> and i<\/code> (1 <= i <= n - 1<\/code>), at most one divider can be installed.<\/p>\n\n\n\n

Divide the corridor into non-overlapping sections, where each section has exactly two seats<\/strong> with any number of plants. There may be multiple ways to perform the division. Two ways are different<\/strong> if there is a position with a room divider installed in the first way but not in the second way.<\/p>\n\n\n\n

Return the number of ways to divide the corridor<\/em>. Since the answer may be very large, return it modulo<\/strong> 109<\/sup> + 7<\/code>. If there is no way, return 0<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> corridor = \"SSPPSPS\"\nOutput:<\/strong> 3\nExplanation:<\/strong> There are 3 different ways to divide the corridor.\nThe black bars in the above image indicate the two room dividers already installed.\nNote that in each of the ways, each<\/strong> section has exactly two<\/strong> seats.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> corridor = \"PPSPSP\"\nOutput:<\/strong> 1\nExplanation:<\/strong> There is only 1 way to divide the corridor, by not installing any additional dividers.\nInstalling any would create some section that does not have exactly two seats.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> corridor = \"S\"\nOutput:<\/strong> 0\nExplanation:<\/strong> There is no way to divide the corridor because there will always be a section that does not have exactly two seats.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • n == corridor.length<\/code><\/li>
  • 1 <= n <= 105<\/sup><\/code><\/li>
  • corridor[i]<\/code> is either 'S'<\/code> or 'P'<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Combination<\/strong><\/h2>\n\n\n\n
    If the 2k-th seat is positioned at j, and the 2k+1-th seat is at i. There are (i – j) ways to split between these two groups.<\/p>\n\n\n\n
    ans = prod{ik<\/sub> – jk<\/sub>}<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int numberOfWays(string corridor) {\n    constexpr int kMod = 1e9 + 7;\n    long ans = 1;\n    long k = 0;\n    for (long i = 0, j = 0; i < corridor.size(); ++i) {\n      if (corridor[i] != 'S') continue;\n      if (++k > 2 && k & 1)\n        ans = ans * (i - j) % kMod;\n      j = i;\n    }\n    return (k >= 2 && k % 2 == 0) ? ans : 0;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters ‘S’ and ‘P’ where each ‘S’ represents a seat and…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[122,31],"class_list":["post-9462","post","type-post","status-publish","format-standard","hentry","category-math","tag-combination","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9462","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=9462"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9462\/revisions"}],"predecessor-version":[{"id":9465,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9462\/revisions\/9465"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9462"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9462"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9462"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}