forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
1930-unique-length-3-palindromic-subsequences.kt
56 lines (47 loc) · 1.69 KB
/
1930-unique-length-3-palindromic-subsequences.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
* Time complexity 0(N * 26) ~ O(N)
*
* Space complexity O(26 + 26 + 26*26) or 0(A^2) where A is the alphabet which technically is O(1)
*/
class Solution {
fun countPalindromicSubsequence(s: String): Int {
val left = HashSet<Char>()
val right = IntArray(26)
var res = HashSet<Pair<Char, Char>>() // inner to outer pair, where they form the palindrome outer-inner-outer
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
}
}
/*
* Time complexity 0(26*N+N*M) where M is the length of the substring between first and last character ~O(N*M)
* I see many posts claiming O(N) for the time complexity of this algorithm, but for Java/Kotlin, time complexity should be O(M*N)
* since according to https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring , substring() time complexity is Linear.
*
* Space complexity O(2*26) ~O(1)
*/
class Solution {
fun countPalindromicSubsequence(s: String): Int {
val first = IntArray(26) {Integer.MAX_VALUE}
val second = IntArray(26)
var res = 0
for(i in s.indices) {
first[s[i] - 'a'] = minOf(first[s[i] - 'a'], i)
second[s[i] - 'a'] = i
}
for(i in 0 until 26) {
if(first[i] < second[i])
res += s.substring(first[i]+1, second[i]).toCharArray().distinct().count()
}
return res
}
}