LeetCode Entry

2147. Number of Ways to Divide a Long Corridor

28.11.2023 hard 2023 kotlin

Count ways to place borders separating pairs of 'S' in 'SP' string

2147. Number of Ways to Divide a Long Corridor hard blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/419

Problem TLDR

Count ways to place borders separating pairs of ‘S’ in ‘SP’ string

Intuition

We can scan linearly and do the interesting stuff after each two ‘S’: each new ‘P’ adds ‘sum’ ways to the total. The last pair of ‘S’ don’t need a border.

  // ssppspsppsspp
  // ss         1
  // ssp        2
  // sspp       3
  //     sps    3
  //     spsp   3+3=6
  //     spspp  6+3=9 <-- return this
  //           ss    9
  //           ssp   9+9=18
  //           sspp  18+9=27 discard this result, as it is last

Approach

Carefult what ‘sum’ to add, save the last sum to a separate variable.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code


  fun numberOfWays(corridor: String): Int {
    var prev = 1
    var sum = 1
    var s = 0
    for (c in corridor)
      if (c == 'S') {
        if (s == 2) {
          prev = sum
          s = 0
        }
        s++
      } else if (s == 2)
        sum = (prev + sum) % 1_000_000_007
    return if (s == 2) prev else 0
  }