Unique Length-3 Palindromic Subsequences - Practice Coding Problems

Unique Length-3 Palindromic Subsequences - Problem

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

Input & Output

Example 1 — Basic Case

$ Input: s = "aabca"

› Output: 3

💡 Note: The 3 palindromic subsequences of length 3 are: "aaa" (using s[0], s[1], s[4]), "aba" (using s[0], s[2], s[4]), and "aca" (using s[0], s[3], s[4]). Note that "aaa" uses the first two 'a's and the last 'a'.

Example 2 — No Palindromes

$ Input: s = "abc"

› Output: 0

💡 Note: There are no characters that appear more than once, so no palindromic subsequences of length 3 can be formed.

Example 3 — Multiple Occurrences

$ Input: s = "bbcacaba"

› Output: 4

💡 Note: The palindromes are: "bab" (b at positions 0,4,7), "bcb" (b at 0,1,7), "bab" (b at 1,4,7), "aca" (a at 2,5,6). Some have multiple ways to form but count as 1 unique palindrome.

Constraints

3 ≤ s.length ≤ 10⁵
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String with characters that may repeat

Pattern

Find ABA patterns where A appears at least twice

Output

Count of unique 3-character palindromes

Key Takeaway

🎯 Key Insight: For each character that appears at least twice, count unique middle characters between its first and last occurrence

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that every length-3 palindrome has the pattern ABA where the outer characters are the same. For each character that appears at least twice, we count how many unique characters exist between its first and last occurrence. The optimal approach uses arrays to track first/last positions efficiently. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Triplets	O(n³)	O(k)	Generate all possible 3-character subsequences and check if they form palindromes
Two Pass with Character Positions	O(n × 26)	O(1)	For each character, find all unique middle characters between its first and last occurrence
Optimized with Arrays	O(n)	O(1)	Use fixed-size arrays for character positions to avoid hash map overhead

Brute Force - Check All Triplets — Algorithm Steps

Iterate through all triplets (i, j, k) where i < j < k
Check if s[i] == s[k] to form palindrome pattern
Use a set to store unique palindromes
Return the size of the set

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Check all combinations (i,j,k) where i < j < k

Palindrome Check

Verify if s[i] == s[k] to form ABA pattern

Store Unique

Add valid palindromes to set to avoid duplicates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    char palindromes[1000][4];  // Store unique palindromes
    int count = 0;
    int n = strlen(s);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (s[i] == s[k]) {
                    char palindrome[4] = {s[i], s[j], s[k], '\0'};
                    
                    // Check if palindrome already exists
                    int exists = 0;
                    for (int p = 0; p < count; p++) {
                        if (strcmp(palindromes[p], palindrome) == 0) {
                            exists = 1;
                            break;
                        }
                    }
                    
                    if (!exists) {
                        strcpy(palindromes[count], palindrome);
                        count++;
                    }
                }
            }
        }
    }
    
    return count;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops to check all possible triplets

⚠ Quadratic Growth

Space Complexity

O(k)

Set to store unique palindromes, where k is number of unique 3-char palindromes

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler