Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1930.html

1930. Unique Length-3 Palindromic Subsequences

Level

Medium

Description

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".

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.

Solution

For each palindromic subsequence of length 3, the first and the last character need to be determined, and the middle character needs to be determined. Loop over s to find each character’s first index and last index. Then for each character, loop over all characters between the character’s first index and last index, and count the number of palindromic subsequences with the current character as the first character and the last character.

  • class Solution {
    public int countPalindromicSubsequence(String s) {
        int[][] startEnd = new int[26][2];
        for (int i = 0; i < 26; i++)
            Arrays.fill(startEnd[i], -1);
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            int index = c - 'a';
            if (startEnd[index][0] < 0)
                startEnd[index][0] = i;
            startEnd[index][1] = i;
        }
        int count = 0;
        for (int i = 0; i < 26; i++) {
            int start = startEnd[i][0], end = startEnd[i][1];
            Set<Character> set = new HashSet<Character>();
            for (int j = start + 1; j < end; j++)
                set.add(s.charAt(j));
            count += set.size();
        }
        return count;
    }
}

############

class Solution {
    public int countPalindromicSubsequence(String s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.indexOf(c), r = s.lastIndexOf(c);
            Set<Character> cs = new HashSet<>();
            for (int i = l + 1; i < r; ++i) {
                cs.add(s.charAt(i));
            }
            ans += cs.size();
        }
        return ans;
    }
}

  • // OJ: https://leetcode.com/problems/unique-length-3-palindromic-subsequences/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int N = s.size(), left[26] = {}, right[26] = {}, seen[26][26] = {}, ans = 0;
        for (int i = 0; i < N; ++i) right[s[i] - 'a']++;
        for (int i = 0; i < N - 1; ++i) {
            int mid = s[i] - 'a';
            right[mid]--;
            if (i > 0) {
                for (int j = 0; j < 26; ++j) {
                    if (left[j] && right[j] && seen[mid][j] == 0) {
                        seen[mid][j] = 1;
                        ++ans;
                    }
                }
            }
            left[mid]++;
        }
        return ans;
    }
};

  • class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        ans = 0
        for c in ascii_lowercase:
            l, r = s.find(c), s.rfind(c)
            if r - l > 1:
                ans += len(set(s[l + 1 : r]))
        return ans

############

# 1930. Unique Length-3 Palindromic Subsequences
# https://leetcode.com/problems/unique-length-3-palindromic-subsequences/

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        res = 0
        n = len(s)
        mp = collections.defaultdict(list)
        
        for i,x in enumerate(s):
            mp[x].append(i)
        
        for key in mp:
            ll = mp[key]
            if len(ll) >= 2:
                ss = set(s[ll[0] + 1 : ll[-1]])     
                res += len(ss)

        return res
        


  • func countPalindromicSubsequence(s string) (ans int) {
	for c := 'a'; c <= 'z'; c++ {
		l, r := strings.Index(s, string(c)), strings.LastIndex(s, string(c))
		cs := map[byte]struct{}{}
		for i := l + 1; i < r; i++ {
			cs[s[i]] = struct{}{}
		}
		ans += len(cs)
	}
	return
}

  • public class Solution {
    public int CountPalindromicSubsequence(string s) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            int l = s.IndexOf(c), r = s.LastIndexOf(c);
            HashSet<char> cs = new HashSet<char>();
            for (int i = l + 1; i < r; ++i) {
                cs.Add(s[i]);
            }
            ans += cs.Count;
        }
        return ans;
    }
}

All Problems

All Solutions