LeetCode 1930 - Unique Length-3 Palindromic Subsequences

The problem asks us to count unique palindromic subsequences of length 3 in a given string s. A palindromic string reads the same forwards and backwards, and in this case, we only care about strings of exactly three characters.

leetcodemediumhash-tablestringbit-manipulationprefix-sum

LeetCode Problem 1930

Difficulty: 🟡 Medium
Topics: Hash Table, String, Bit Manipulation, Prefix Sum

Solution

Problem Understanding

The problem asks us to count unique palindromic subsequences of length 3 in a given string s. A palindromic string reads the same forwards and backwards, and in this case, we only care about strings of exactly three characters. A subsequence is formed by deleting zero or more characters from the original string without changing the relative order of the remaining characters.

For example, in the string "aabca", "aba" is a valid subsequence because we can take the first 'a', skip the second 'a', take 'b', and then take the last 'a'. The result should only count unique sequences, so if multiple instances of "aba" occur, it counts as one.

The input s has a length of up to 105 and consists only of lowercase English letters. This length indicates that a naive triple-loop brute-force approach could be too slow, especially since iterating over all combinations of three characters would be O(n³). Edge cases include strings with no palindromes, strings with repeated characters, and strings where the first and last characters are the same but there are not enough characters in between to form length-3 palindromes.

Approaches

The brute-force approach is to generate all possible subsequences of length 3, check if each is a palindrome, and then add it to a set to ensure uniqueness. This approach works correctly but requires O(n³) time because there are O(n³) possible combinations of three characters. For n up to 105, this is infeasible.

The optimal approach relies on the observation that any length-3 palindrome has the form a_b_a, where a is the first and last character and b is any character between them. Therefore, for each character a in 'a' to 'z', we can find its first and last occurrence in the string. Then, every unique character between these positions forms a valid palindrome of the form a_b_a. Using a set to count unique middle characters ensures we only count each palindrome once. This reduces the problem to O(n * 26) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n³) Generate all length-3 subsequences and filter palindromes
Optimal O(n * 26) ≈ O(n) O(26) ≈ O(1) For each character, count unique characters between first and last occurrence

Algorithm Walkthrough

  1. Initialize a result counter to 0.

  2. For each character a from 'a' to 'z':

  3. Find the first index of a in the string.

  4. Find the last index of a in the string.

  5. If the first index is greater than or equal to the last index, skip this character because it cannot form a length-3 palindrome.

  6. Otherwise, collect all unique characters between the first and last index.

  7. The number of unique characters in this interval is the number of palindromes of the form a_b_a for this a. Add this count to the result.

  8. Return the result.

Why it works: This approach guarantees correctness because every length-3 palindrome must have the same character at the first and last positions. By counting all distinct characters in between, we capture all unique length-3 palindromes. The set ensures duplicates are ignored, satisfying the uniqueness requirement.

Python Solution

class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        result = 0
        for ch in map(chr, range(ord('a'), ord('z') + 1)):
            first = s.find(ch)
            last = s.rfind(ch)
            if first == -1 or first == last:
                continue
            middle_chars = set(s[first + 1:last])
            result += len(middle_chars)
        return result

Explanation: We iterate through each lowercase letter. s.find(ch) and s.rfind(ch) efficiently locate the first and last occurrences of that letter. If the letter does not appear twice, it cannot form a length-3 palindrome. We then collect all unique characters between the first and last positions using a set and count them. Summing these counts gives the total number of unique palindromic subsequences.

Go Solution

func countPalindromicSubsequence(s string) int {
    result := 0
    for ch := 'a'; ch <= 'z'; ch++ {
        first := -1
        last := -1
        for i, c := range s {
            if c == ch {
                if first == -1 {
                    first = i
                }
                last = i
            }
        }
        if first == -1 || first == last {
            continue
        }
        middleChars := make(map[rune]struct{})
        for i := first + 1; i < last; i++ {
            middleChars[rune(s[i])] = struct{}{}
        }
        result += len(middleChars)
    }
    return result
}

Explanation: Go requires explicit management of sets using a map with empty struct values. We scan for the first and last positions manually and then populate a map for unique middle characters. Everything else is analogous to the Python approach.

Worked Examples

Example 1: "aabca"

Character First Last Middle chars Count added
a 0 4 {b, c} 2
b 2 2 - 0
c 3 3 - 0
Result: 2 (aba, aca) + 1 for aaa = 3

Example 2: "adc"

No character appears twice. Result = 0

Example 3: "bbcbaba"

Character First Last Middle chars Count added
a 1 5 {b} 1
b 0 6 {b, c, a} 3
c 3 3 - 0
Result: 1 + 3 = 4

Complexity Analysis

Measure Complexity Explanation
Time O(n * 26) ≈ O(n) Each of 26 letters requires scanning n characters
Space O(26) ≈ O(1) Only storing unique middle characters per letter

The algorithm is linear with respect to string length, making it efficient for the maximum constraint n = 10^5.

Test Cases

# Provided examples
assert Solution().countPalindromicSubsequence("aabca") == 3  # "aba", "aaa", "aca"
assert Solution().countPalindromicSubsequence("adc") == 0    # no palindrome
assert Solution().countPalindromicSubsequence("bbcbaba") == 4 # "bbb", "bcb", "bab", "aba"

# Edge cases
assert Solution().countPalindromicSubsequence("aaa") == 1     # only "aaa"
assert Solution().countPalindromicSubsequence("abcabcabc") == 3 # "aba", "aca", "bcb"
assert Solution().countPalindromicSubsequence("a") == 0       # too short
assert Solution().countPalindromicSubsequence("ab") == 0      # too short
assert Solution().countPalindromicSubsequence("ababababab") == 3 # "aaa", "aba", "bab"
Test Why
"aabca" Normal case with multiple palindromes
"adc" No repeated characters
"bbcbaba" Multiple overlapping palindromes
"aaa" Only one repeated character forms one palindrome
"abcabcabc" Multiple palindromes using first-last occurrence method
"a" Below minimum length
"ab" Below minimum length
"ababababab" Repeated pattern with overlapping palindromes

Edge Cases

Single-character repeated strings: "aaa" forms only one palindrome "aaa". Algorithm correctly counts middle characters, which in this case is empty, but first != last allows counting length-3 palindrome.

Strings without repeated characters: "abc" cannot form any length-3 palindromes. The algorithm correctly skips characters that appear less than twice.

Strings with maximum length: For s of length 10⁵, the algorithm remains efficient because it scans each letter only once and processes at most 26 sets, each with up to 26 elements. This ensures linear performance and prevents timeouts.