[LeetCode][Kotlin] 1930. Unique Length-3 Palindromic Subsequences

1930. Unique Length-3 Palindromic Subsequences

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

 

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

 

A palindrome is a string that reads the same forwards and backwards.

 

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

문자열 s가 주어지면 s의 하위 시퀀스인 길이가 3인 고유 회문의 수를 반환합니다. 

동일한 하위 시퀀스를 얻는 방법이 여러 가지 있더라도 여전히 한 번만 계산됩니다. 

회문은 앞으로 읽어도 뒤로 읽어도 같은 문자열입니다. 

문자열의 하위 시퀀스는 나머지 문자의 상대적 순서를 변경하지 않고 일부 문자가 삭제된(없음일 수 없음) 원래 문자열에서 생성된 새 문자열입니다. 
- 예를 들어, "ace"는 "abcde"의 하위 시퀀스입니다.

 

Example 1:

Input: s = "aabca"

Output: 3

Explanation: The 3 palindromic subsequences of length 3 are:

- "aba" (subsequence of "aabca")

- "aaa" (subsequence of "aabca")

- "aca" (subsequence of "aabca")

 

Example 2:

Input: s = "adc"

Output: 0

Explanation: There are no palindromic subsequences of length 3 in "adc".

 

Example 3:

Input: s = "bbcbaba"

Output: 4

Explanation: The 4 palindromic subsequences of length 3 are:

- "bbb" (subsequence of "bbcbaba")

- "bcb" (subsequence of "bbcbaba")

- "bab" (subsequence of "bbcbaba")

- "aba" (subsequence of "bbcbaba")

 

Constraints:

• 3 <= s.length <= 10^5
• s consists of only lowercase English letters.

---

코드 1

• 문자열에서 중복을 제거하고, 일치하는 문자의 첫 번째 인덱스와 마지막 인덱스를 비교한다.
• 두 인덱스의 값이 같다면, 해당 문자는 하나다.
• 같지 않다면 두 인덱스 사이의 위치한 문자들만큼 회문을 만들 수 있다.
• 그리고 고유 회문 쌍을 구하기 위해서 두 인덱스 사이의 중복된 문자를 제거해야 한다.

class Solution {
    fun countPalindromicSubsequence(s: String): Int {
        val hs = HashSet<Pair<Char, Char>>()
        val set = s.toSet()

        set.forEach { c ->
            val first = s.indexOfFirst { it == c }
            val last = s.indexOfLast { it == c }
            if (first != last) {
                for (i in first + 1 until last) {
                    hs.add(Pair(c, s[i]))
                }
            }
        }

        return hs.size
    }
}

 

코드 2

• 현재까지 처리한 문자들을 저장하는 left 와 각 문자의 남은 개수를 저장하는 right 를 만든다.
• 문자열을 순회하면서 right 배열에 현재 문자의 개수를 감소시킨다.
• 26개의 알파벳 문자을 반복하면서 회문의 양쪽에 위치하는 문자(c)가 맞다면, 회문의 중간 문자(s[i])를 추가한다.

class Solution {
    fun countPalindromicSubsequence2(s: String): Int {
        val res = HashSet<Pair<Char, Char>>()
        val left = HashSet<Char>()

        val right = IntArray(26)
        for (c in s) {
            right[c - 'a']++
        }

        for (i in s.indices) {
            if (right[s[i] - 'a'] > 0) {
                right[s[i] - 'a']--
            }

            for (j in 0 until 26) {
                val c = 'a'.plus(j)
                if (c in left && right[c - 'a'] > 0) {
                    res.add(s[i] to c)
                }
            }

            left.add(s[i])
        }

        return res.size
    }
}