LeetCode Entry

1930. Unique Length-3 Palindromic Subsequences

14.11.2023 medium 2023 kotlin

Count of unique palindrome substrings of length 3

1930. Unique Length-3 Palindromic Subsequences medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/403

Problem TLDR

Count of unique palindrome substrings of length 3

Intuition

We can count how many other characters between group of the current

Approach

Let’s use Kotlin API:

  • groupBy
  • filterValues
  • indexOf
  • lastIndexOf

Complexity

  • Time complexity: \(O(n)\), we can also use withIndex to avoid searching indexOf and lastIndexOf.

  • Space complexity: \(O(1)\), if we store frequencies in an IntArray

Code


    fun countPalindromicSubsequence(s: String): Int {
      val freq = s.groupBy { it }.filterValues { it.size > 1 }
      var count = 0
      for ((l, f) in freq) {
        if (f.size > 2) count++
        val visited = HashSet<Char>()
        for (i in s.indexOf(l)..s.lastIndexOf(l))
          if (s[i] != l && visited.add(s[i])) count++
      }
      return count
    }