aboutsummaryrefslogtreecommitdiff
path: root/unique_len_3_palindrome.c
diff options
context:
space:
mode:
Diffstat (limited to 'unique_len_3_palindrome.c')
-rw-r--r--unique_len_3_palindrome.c44
1 files changed, 44 insertions, 0 deletions
diff --git a/unique_len_3_palindrome.c b/unique_len_3_palindrome.c
new file mode 100644
index 0000000..2f8efc9
--- /dev/null
+++ b/unique_len_3_palindrome.c
@@ -0,0 +1,44 @@
+// 1930. Unique Length-3 Palindromic Subsequences
+#include "leetcode.h"
+
+/*
+ * given a string 's', return the number of unique palindromes of length three
+ * that 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 thhe
+ * remaining characters. for example: "ace" is a subsequence of "abcde"
+ */
+
+int countPalindromicSubsequence(char *s) {
+ int n = strlen(s), ans = 0;
+ bool *alpha = calloc(26, sizeof(bool));
+ bool *tmp;
+ for (int i = 0; i < n; i++) {
+ if (alpha[s[i] - 'a'])
+ continue;
+ alpha[s[i] - 'a'] = 1;
+ char c = s[i];
+ for (int j = n - 1; j > i + 1; j--) {
+ if (s[j] == s[i]) {
+ tmp = calloc(26, sizeof(char));
+ for (int k = i + 1; k < j; k++) {
+ if (!tmp[s[k] - 'a']) {
+ tmp[s[k] - 'a'] = 1;
+ ans++;
+ }
+ }
+ break;
+ }
+ }
+ }
+ return ans;
+}
+
+int main() {
+ char s1[] = {"aabca"}, s2[] = {"adc"}, s3[] = {"bbcbaba"};
+ printf("%d\n", countPalindromicSubsequence(s1)); // expect: 3
+ printf("%d\n", countPalindromicSubsequence(s2)); // expect: 0
+ printf("%d\n", countPalindromicSubsequence(s3)); // expect: 4
+}