There's this problem on leetocde: 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.
to solve it: find. first and last occurence of a letter, count the distinc unique letters in between , don't forget the account for the same letter as well so like "aaa"
I wrote this solution to it:
func countPalindromicSubsequence(s string) int {
p := make(map[rune][2]int)
o := make(map[rune]int)
total := 0
for i, v := range s {
o[v]++
_, ok := p[v]
if !ok {
/// this is the first time we record this number
s :=[2]int{i,0}
p[v] = s
}else {
s := p[v]
s[1] = i
p[v] = s
}
}
for k,v := range p {
if v[1] == 0 {
continue
}
if o[k] >= 3 {
total++
}
//// count palindromes in between
for l, value := range p {
if l != k && ((value[0] > v[0] && value[0] < v[1]) || (value[1] > v[0] && value[1] < v[1])){
total ++
}
}
}
return total
}
Code Explanation:
in map p, I save the letters that occurred in the string, along with their first and last occurrence index. if the letter appears once, the second index will be kept zero
in the map o , I am saving the number of occurrences of every letter. so if letter a appears 5 times. p["a"] would be equal to {first_index, last_index}, o["a"] would be equal to 5
while looping over p, I check if the letter has occured twice by using
if v[1] == 0 {
continue
}
if it has occured twice, it means that this letter is a candidate for palindrome formation. I loop again over p to check the letter that have appeared between the letters first and last occurence, and those are palindromes.
As for o, I use it to check wether the same has formed a palindrome like "aaa" it fails on "tlpjzdmtwderpkpmgoyrcxttiheassztncqvnfjeyxxp" I am debugging it, but no luck anyone can help?
There's this problem on leetocde: 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.
to solve it: find. first and last occurence of a letter, count the distinc unique letters in between , don't forget the account for the same letter as well so like "aaa"
I wrote this solution to it:
func countPalindromicSubsequence(s string) int {
p := make(map[rune][2]int)
o := make(map[rune]int)
total := 0
for i, v := range s {
o[v]++
_, ok := p[v]
if !ok {
/// this is the first time we record this number
s :=[2]int{i,0}
p[v] = s
}else {
s := p[v]
s[1] = i
p[v] = s
}
}
for k,v := range p {
if v[1] == 0 {
continue
}
if o[k] >= 3 {
total++
}
//// count palindromes in between
for l, value := range p {
if l != k && ((value[0] > v[0] && value[0] < v[1]) || (value[1] > v[0] && value[1] < v[1])){
total ++
}
}
}
return total
}
Code Explanation:
in map p, I save the letters that occurred in the string, along with their first and last occurrence index. if the letter appears once, the second index will be kept zero
in the map o , I am saving the number of occurrences of every letter. so if letter a appears 5 times. p["a"] would be equal to {first_index, last_index}, o["a"] would be equal to 5
while looping over p, I check if the letter has occured twice by using
if v[1] == 0 {
continue
}
if it has occured twice, it means that this letter is a candidate for palindrome formation. I loop again over p to check the letter that have appeared between the letters first and last occurence, and those are palindromes.
As for o, I use it to check wether the same has formed a palindrome like "aaa" it fails on "tlpjzdmtwderpkpmgoyrcxttiheassztncqvnfjeyxxp" I am debugging it, but no luck anyone can help?
For the record, this is LeetCode 1930. Unique Length-3 Palindromic Subsequences problem.
To solve this problem, note that a palindromic subsequence of length 3 looks like x...x, where ... represents one or more letters. The number of such subsequence is given by j - i - 1, where i is the index of the first x and j is the last.
Therefore, we first iterate over the string and collect the first and last indices for every letter in a hash map. Then for each of the index pairs, count the number of unique letters in between those indices.
Following is a Python and a Golang solution. My Go is a little rusty, so, there may be a smarter/more concise way to write the code.
def countPalindromicSubsequence(s: str) -> int:
indices: dict[int, list[int]] = {}
for i, c in enumerate(s):
x = indices.get(c, [i, i])
x[1] = i
indices[c] = x
return sum(len(set(s[start + 1: end])) for start, end in indices.values() if start != end)
func countPalindromicSubsequence(s string) int {
indices := make(map[rune][]int)
for i, c := range s {
x, ok := indices[c]
if !ok {
x = []int{i, i}
}
x[1] = i
indices[c] = x
}
count := 0
for _, v := range indices {
start, end := v[0], v[1]
if start != end {
uniqueChars := make(map[rune]bool)
for _, c := range s[start+1 : end] {
uniqueChars[c] = true
}
count += len(uniqueChars)
}
}
return count
}
The problem states that the string s only consists of lower case letters, so, the hash map will contain no more than 26 letters. Thus, the above algorithm runs in linear time (O(n)), and uses only constant space (O(1)).
o,pare not very enlightening... I don't understand why you would need to loop overpin a nested loop again. What does that have to do with counting palindromes? – trincot Commented Jan 4 at 22:04