LeetCode Entry

1759. Count Number of Homogenous Substrings

09.11.2023 medium 2023 kotlin

Count of substrings of same chars

1759. Count Number of Homogenous Substrings medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/398

Problem TLDR

Count of substrings of same chars

Intuition

Just count current len and add to total

  // abbcccaa   c t
  // a          1 1
  //  b         1 2
  //   b        2 4
  //    c       1 5
  //     c      2 7
  //      c     3 10
  //       a    1 11
  //        a   2 13

Approach

  • don’t forget to update prev

Complexity

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

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

Code


  fun countHomogenous(s: String): Int {
    var total = 0
    var count = 0
    var prev = '.'
    for (c in s) {
      if (c == prev) count++
      else count = 1
      total = (total + count) % 1_000_000_007
      prev = c
    }
    return total
  }